Matrix multiplication with @ operator in NumPy - Time & Space Complexity

Time Complexity: Matrix multiplication with @ operator

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to multiply two matrices grows as the size of the matrices increases.

How does the number of calculations change when the matrices get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

n = 10  # example size
A = np.random.rand(n, n)
B = np.random.rand(n, n)

C = A @ B

This code multiplies two square matrices A and B of size n by n using the @ operator.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying and summing elements for each cell in the result matrix.
• How many times: For each of the n rows and n columns, it performs n multiplications and additions.

How Execution Grows With Input

As the matrix size n grows, the number of calculations grows quickly because each new row and column adds many more multiplications.

Input Size (n)	Approx. Operations
10	About 1,000
100	About 1,000,000
1000	About 1,000,000,000

Pattern observation: The operations grow roughly by the cube of n, so doubling n makes the work about eight times bigger.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to multiply two n by n matrices grows roughly with the cube of n, so bigger matrices take much more time.

Common Mistake

[X] Wrong: "Matrix multiplication with @ operator runs in linear time like simple addition."

[OK] Correct: Multiplying matrices involves many nested calculations, not just one pass through the data, so it takes much more time as size grows.

Interview Connect

Understanding how matrix multiplication scales helps you explain performance in data science tasks like machine learning and graphics, showing you know how big data affects calculations.

Self-Check

"What if we multiply a matrix of size n by another matrix of size n by m? How would the time complexity change?"

Practice

1. What does the @ operator do in numpy when applied between two arrays?

easy

A. Performs matrix multiplication if shapes are compatible

B. Adds the two arrays element-wise

C. Calculates the element-wise product

D. Computes the transpose of the first array

Solution

1. Step 1: Understand the @ operator purpose

   The @ operator in numpy is designed for matrix multiplication, which requires the inner dimensions of the two arrays to match.

2. Step 2: Differentiate from other operations

   Element-wise addition or multiplication use + or * respectively, not @. Transpose uses .T.

3. Final Answer:

   Performs matrix multiplication if shapes are compatible -> Option A

4. Quick Check:

   @ means matrix multiply [OK]

Hint: Remember: @ means matrix multiply, not element-wise [OK]

Common Mistakes:

• Confusing @ with element-wise multiplication
• Thinking @ adds arrays
• Assuming @ transposes arrays

2. Which of the following is the correct syntax to multiply two numpy arrays A and B using the @ operator?

easy

A. C = A * B

B. C = A + B

C. C = A.dot(B)

D. C = A @ B

Solution

1. Step 1: Identify the @ operator usage

   The @ operator is used as C = A @ B to perform matrix multiplication in numpy.

2. Step 2: Differentiate from other operations

   A * B is element-wise multiplication, A.dot(B) is a method but not using @, and A + B is addition.

3. Final Answer:

   C = A @ B -> Option D

4. Quick Check:

   Use @ between arrays for matrix multiply [OK]

Hint: Use @ directly between arrays for matrix multiply [OK]

Common Mistakes:

• Using * instead of @ for matrix multiply
• Confusing method dot() with operator @
• Using addition operator + mistakenly

3. What is the output of the following code?

import numpy as np
A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])
C = A @ B
print(C)

medium

A. [[ 5 12]
[21 32]]

B. [[ 6 8]
[10 12]]

C. [[19 22]
[43 50]]

D. [[ 5 6]
[ 7 8]]

Solution

1. Step 1: Calculate matrix multiplication manually

   Multiply rows of A by columns of B:
   First row: (1*5 + 2*7) = 19, (1*6 + 2*8) = 22
   Second row: (3*5 + 4*7) = 43, (3*6 + 4*8) = 50

2. Step 2: Confirm output matches calculation

   The resulting matrix is [[19, 22], [43, 50]], which matches [[19 22] [43 50]].

3. Final Answer:

   [[19 22] [43 50]] -> Option C

4. Quick Check:

   Matrix multiply result = [[19 22] [43 50]] [OK]

Hint: Multiply rows by columns and sum for each element [OK]

Common Mistakes:

• Adding elements instead of multiplying and summing
• Mixing element-wise multiplication with matrix multiplication
• Confusing row and column order

4. What error will occur when running this code?

import numpy as np
A = np.array([[1, 2, 3], [4, 5, 6]])
B = np.array([[7, 8], [9, 10]])
C = A @ B

medium

A. ValueError: shapes (2,3) and (2,2) not aligned for matrix multiplication

B. TypeError: unsupported operand type(s) for @

C. No error, output is a (2,2) matrix

D. IndexError: index out of bounds

Solution

1. Step 1: Check shapes of arrays

   Array A shape is (2,3), array B shape is (2,2). For matrix multiplication, A's columns (3) must equal B's rows (2).

2. Step 2: Identify mismatch and error

   Since 3 != 2, numpy raises a ValueError about shape misalignment.

3. Final Answer:

   ValueError: shapes (2,3) and (2,2) not aligned for matrix multiplication -> Option A

4. Quick Check:

   Matrix multiply needs matching inner dimensions [OK]

Hint: Check inner dimensions match before using @ [OK]

Common Mistakes:

• Ignoring shape mismatch and expecting output
• Confusing element-wise multiplication with matrix multiplication
• Assuming @ works like addition

5. Given two numpy arrays:

A = np.array([[1, 0], [0, 1]])
B = np.array([[2, 3], [4, 5]])

What is the result of C = A @ B @ A?

hard

A. [[5 8]
[9 14]]

B. [[2 3]
[4 5]]

C. [[1 0]
[0 1]]

D. [[2 4]
[3 5]]

Solution

1. Step 1: Multiply A and B

   Matrix A is the identity matrix. Multiplying identity with B returns B:
   A @ B = B = [[2, 3], [4, 5]]

2. Step 2: Multiply result by A again

   Multiplying B by identity matrix A again returns B:
   B @ A = B = [[2, 3], [4, 5]]

3. Final Answer:

   [[2 3] [4 5]] -> Option B

4. Quick Check:

   Identity matrix leaves other matrix unchanged [OK]

Hint: Identity matrix A leaves matrix unchanged when multiplied [OK]

Common Mistakes:

• Multiplying incorrectly and swapping rows/columns
• Assuming multiplication changes matrix when identity is involved
• Confusing element-wise and matrix multiplication