Matrix multiplication (*) in MATLAB - Time & Space Complexity

Time Complexity: Matrix multiplication (*)

O(n^3)

Understanding Time Complexity

Matrix multiplication is a common operation in many programs. Understanding how its time grows helps us write faster code.

We want to know how the work needed changes as the matrix size gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

A = rand(n, n);
B = rand(n, n);
C = A * B;

This code multiplies two square matrices of size n by n using MATLAB's built-in operator.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying and adding elements for each entry in the result matrix.
• How many times: For each of the n rows and n columns, it sums n products, so about n x n x n = n³ times.

How Execution Grows With Input

As the matrix size n grows, the number of operations grows much faster.

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

Pattern observation: When n increases ten times, the work increases about a thousand times.

Final Time Complexity

Time Complexity: O(n^3)

This means the time needed grows roughly with the cube of the matrix size.

Common Mistake

[X] Wrong: "Matrix multiplication takes only n² steps because the result is an n by n matrix."

[OK] Correct: Each element in the result needs n multiplications and additions, so the total work is much more than just filling the matrix.

Interview Connect

Knowing how matrix multiplication scales helps you understand performance in many areas like graphics, data science, and simulations. It shows you how to think about efficiency in real problems.

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. Which of the following statements about matrix multiplication in MATLAB is correct?

easy

A. Matrix multiplication uses the operator .* in MATLAB.

B. The number of columns in the first matrix must equal the number of rows in the second matrix.

C. You can multiply any two matrices regardless of their sizes.

D. Matrix multiplication always produces a matrix of the same size as the first matrix.

Solution

1. Step 1: Understand matrix multiplication size rules

   Matrix multiplication requires the number of columns in the first matrix to match the number of rows in the second matrix.

2. Step 2: Identify correct operator and output size

   The operator for matrix multiplication is *, not .*, and the output size depends on the rows of the first and columns of the second matrix.

3. Final Answer:

   The number of columns in the first matrix must equal the number of rows in the second matrix. -> Option B

4. Quick Check:

   Matrix size rule = The number of columns in the first matrix must equal the number of rows in the second matrix. [OK]

Hint: Check matrix sizes: cols of first = rows of second [OK]

Common Mistakes:

• Confusing element-wise (.*) with matrix multiplication (*)
• Ignoring matrix size compatibility
• Assuming output size equals first matrix size

2. Which of the following MATLAB commands correctly multiplies matrix A by matrix B?

easy

A. C = A * B;

B. C = A .* B;

C. C = A + B;

D. C = A / B;

Solution

1. Step 1: Identify the correct operator for matrix multiplication

   In MATLAB, * is used for matrix multiplication, while .* is for element-wise multiplication.

2. Step 2: Confirm the correct syntax

   The command C = A * B; correctly multiplies matrices A and B.

3. Final Answer:

   C = A * B; -> Option A

4. Quick Check:

   Matrix multiply uses * operator [OK]

Hint: Use * for matrix multiply, .* for element-wise multiply [OK]

Common Mistakes:

• Using .* instead of * for matrix multiplication
• Using + or / operators incorrectly for multiplication
• Syntax errors with missing semicolons

3. What is the result of the following MATLAB code?

A = [1 2; 3 4];
B = [5 6; 7 8];
C = A * B;

medium

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

B. [[12 16]; [20 24]]

C. [[6 8]; [10 12]]

D. [[19 22]; [43 50]]

Solution

1. Step 1: Multiply rows of A by columns of B

   Calculate each element: C(1,1) = 1*5 + 2*7 = 19; C(1,2) = 1*6 + 2*8 = 22; C(2,1) = 3*5 + 4*7 = 43; C(2,2) = 3*6 + 4*8 = 50.

2. Step 2: Form the resulting matrix

   The resulting matrix C is [[19 22]; [43 50]].

3. Final Answer:

   [[19 22]; [43 50]] -> Option D

4. Quick Check:

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

Hint: Multiply rows by columns and sum products [OK]

Common Mistakes:

• Adding matrices instead of multiplying
• Using element-wise multiplication results
• Mixing up row and column indices

4. Consider the MATLAB code below. What is the error and how to fix it?

A = [1 2 3; 4 5 6];
B = [7 8; 9 10];
C = A * B;

medium

A. Error: Use .* instead of * for multiplication.

B. No error, code runs correctly.

C. Error: Matrix dimensions must agree. Fix by making B a 3xN matrix.

D. Error: Use plus (+) instead of multiplication.

Solution

1. Step 1: Check matrix sizes for multiplication

   A is 2x3, B is 2x2. Number of columns in A (3) does not equal number of rows in B (2), so multiplication is invalid.

2. Step 2: Fix the error by adjusting B's size

   To multiply, B must have 3 rows. For example, B could be 3x2 matrix.

3. Final Answer:

   Error: Matrix dimensions must agree. Fix by making B a 3xN matrix. -> Option C

4. Quick Check:

   Matrix size mismatch error = Error: Matrix dimensions must agree. Fix by making B a 3xN matrix. [OK]

Hint: Check cols of A = rows of B before multiplying [OK]

Common Mistakes:

• Ignoring dimension mismatch errors
• Trying to use .* instead of * to fix size errors
• Assuming multiplication works for any sizes

5. You have two matrices:

A = [1 0 2; -1 3 1];
B = [3 1; 2 1; 1 0];

Calculate the product C = A * B and identify the element at position (2,1) in matrix C.

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Verify matrix sizes for multiplication

   A is 2x3, B is 3x2, so multiplication is valid and result C will be 2x2.

2. Step 2: Calculate element C(2,1)

   Multiply row 2 of A by column 1 of B: (-1)*3 + 3*2 + 1*1 = -3 + 6 + 1 = 4.

3. Step 3: Recalculate carefully

   Recheck calculation: (-1)*3 = -3, 3*2 = 6, 1*1 = 1; sum = 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   Sum products for C(2,1) = 4 [OK]

Hint: Multiply row 2 of A by column 1 of B and sum [OK]

Common Mistakes:

• Mixing row and column indices
• Forgetting negative signs in multiplication
• Adding wrong elements or missing terms