Matrix multiplication (%*%) in R Programming - 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 better code.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Multiply two square matrices A and B of size n x n
n <- 3
A <- matrix(1:(n*n), n, n)
B <- matrix((n*n):1, n, n)
C <- A %*% B
    

This code multiplies two square matrices using R's built-in matrix multiplication 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 repeats n multiplications and additions.

How Execution Grows With Input

As the matrix size n grows, the number of operations grows quickly because each cell needs n calculations.

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

Pattern observation: The work grows very fast, roughly by the cube of n.

Final Time Complexity

Time Complexity: O(n^3)

This means if the matrix size doubles, the work needed grows about eight times.

Common Mistake

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

[OK] Correct: Each cell in the result needs n multiplications and additions, so the total steps multiply to n cubed.

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 work growing with input size.

Self-Check

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

Practice

1. What does the operator %*% do in R?

easy

A. It multiplies two matrices using matrix multiplication rules.

B. It adds two matrices element-wise.

C. It multiplies two numbers element-wise.

D. It transposes a matrix.

Solution

1. Step 1: Understand the operator %*%

   The operator %*% in R is specifically used for matrix multiplication, not element-wise operations or addition.

2. Step 2: Differentiate from other operations

   Element-wise multiplication uses * and addition uses +. Transpose uses t(). So %*% is for matrix multiplication.

3. Final Answer:

   It multiplies two matrices using matrix multiplication rules. -> Option A

4. Quick Check:

   %*% = matrix multiplication [OK]

Hint: Remember %*% means matrix multiplication, not element-wise [OK]

Common Mistakes:

• Confusing %*% with element-wise multiplication (*)
• Thinking %*% adds matrices
• Using %*% to transpose matrices

2. Which of the following is the correct syntax to multiply two matrices A and B in R?

easy

A. A * B

B. A %/% B

C. A + B

D. A %*% B

Solution

1. Step 1: Identify matrix multiplication syntax

   In R, matrix multiplication uses the operator %*% between two matrices.

2. Step 2: Check other operators

   * is element-wise multiplication, + is addition, and %/% is integer division, so they are incorrect for matrix multiplication.

3. Final Answer:

   A %*% B -> Option D

4. Quick Check:

   Matrix multiply = A %*% B [OK]

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

Common Mistakes:

• Using * instead of %*% for matrix multiplication
• Using + or %/% operators mistakenly
• Forgetting spaces around %*%

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

A <- matrix(c(1, 2, 3, 4), nrow=2, ncol=2)
B <- matrix(c(5, 6, 7, 8), nrow=2, ncol=2)
C <- A %*% B
print(C)

medium

A. [[6, 8], [10, 12]]

B. [[5, 12], [21, 32]]

C. [[23, 31], [34, 46]]

D. [[12, 14], [16, 18]]

Solution

1. Step 1: Construct matrices A and B (column-major order)

   A = [[1, 3], [2, 4]]
   B = [[5, 7], [6, 8]]

2. Step 2: Compute matrix multiplication

   C[1,1] = 1*5 + 3*6 = 5 + 18 = 23
   C[1,2] = 1*7 + 3*8 = 7 + 24 = 31
   C[2,1] = 2*5 + 4*6 = 10 + 24 = 34
   C[2,2] = 2*7 + 4*8 = 14 + 32 = 46

3. Final Answer:

   [[23, 31], [34, 46]] -> Option C

4. Quick Check:

   Matrix multiply result = [[23,31],[34,46]] [OK]

Hint: Remember R fills matrices by column, not row [OK]

Common Mistakes:

• Assuming row-wise filling of matrices
• Mixing element-wise and matrix multiplication
• Incorrect multiplication order

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

A <- matrix(1:6, nrow=2, ncol=3)
B <- matrix(1:4, nrow=2, ncol=2)
C <- A %*% B

medium

A. Error: Syntax error; fix by adding commas in matrix() calls.

B. Error: Non-conformable arguments; fix by making A's columns equal B's rows.

C. No error; code runs fine and returns a 2x2 matrix.

D. Error: Cannot multiply matrices with different number of rows; fix by transposing B.

Solution

1. Step 1: Check matrix dimensions

   A is 2x3, B is 2x2. For matrix multiplication, A's columns (3) must equal B's rows (2). They don't match.

2. Step 2: Identify error and fix

   R will give 'non-conformable arguments' error. To fix, B must have 3 rows or A must have 2 columns. For example, B <- matrix(1:6, nrow=3, ncol=2).

3. Final Answer:

   Error: Non-conformable arguments; fix by making A's columns equal B's rows. -> Option B

4. Quick Check:

   Matrix dims must match inner dimensions [OK]

Hint: Check if A's columns = B's rows before multiplying [OK]

Common Mistakes:

• Ignoring dimension mismatch
• Trying to multiply incompatible matrices
• Assuming R auto-adjusts matrix sizes

5. You have two matrices:

M1 <- matrix(c(2, 0, 1, 3, 4, 5), nrow=2, ncol=3)
M2 <- matrix(c(1, 2, 3, 4, 5, 6), nrow=3, ncol=2)

What is the resulting matrix when you compute M1 %*% M2?

hard

A. [[16, 37], [21, 45]]

B. [[8, 12], [39, 54]]

C. [[5, 10], [29, 40]]

D. [[2, 4], [3, 6]]

Solution

1. Step 1: Construct matrices M1 and M2 (column-major order)

   M1 = [[2, 1, 4], [0, 3, 5]]
   M2 = [[1, 4], [2, 5], [3, 6]]

2. Step 2: Compute each element of the product

   C[1,1] = 2*1 + 1*2 + 4*3 = 2 + 2 + 12 = 16
   C[1,2] = 2*4 + 1*5 + 4*6 = 8 + 5 + 24 = 37
   C[2,1] = 0*1 + 3*2 + 5*3 = 0 + 6 + 15 = 21
   C[2,2] = 0*4 + 3*5 + 5*6 = 0 + 15 + 30 = 45

3. Final Answer:

   [[16, 37], [21, 45]] -> Option A

4. Quick Check:

   Matrix multiply result = [[16,37],[21,45]] [OK]

Hint: Remember R fills matrices by column, check carefully [OK]

Common Mistakes:

• Assuming row-wise filling instead of column-wise
• Mixing element-wise and matrix multiplication
• Misaligning matrix dimensions