Matrix rank and null space in MATLAB - Time & Space Complexity

Time Complexity: Matrix rank and null space

O(n^3)

Understanding Time Complexity

We want to understand how the time to find a matrix's rank and null space changes as the matrix gets bigger.

How does the work grow when the matrix size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

A = rand(n);  % Create an n-by-n random matrix
r = rank(A);  % Find the rank of matrix A
N = null(A);  % Find the null space of matrix A
    

This code creates a square matrix and calculates its rank and null space.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The main work is done inside the rank and null functions, which use matrix factorizations like Gaussian elimination or singular value decomposition.
• How many times: These factorizations process the entire n-by-n matrix, working through rows and columns multiple times.

How Execution Grows With Input

As the matrix size n grows, the number of operations grows quickly because the methods look at many pairs of rows and columns.

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: When n doubles, the work grows roughly by n cubed, so it gets much bigger very fast.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to find rank and null space grows roughly with the cube of the matrix size.

Common Mistake

[X] Wrong: "Finding rank or null space is quick and grows linearly with matrix size."

[OK] Correct: These operations involve complex steps that look at many parts of the matrix together, so the time grows much faster than just the size.

Interview Connect

Knowing how matrix operations scale helps you understand performance in data science and engineering tasks, showing you can think about efficiency in real problems.

Self-Check

"What if the matrix is sparse instead of full? How would the time complexity change?"

Practice

1. What does the rank function in MATLAB tell you about a matrix?

easy

A. The number of linearly independent rows or columns

B. The total number of elements in the matrix

C. The sum of all elements in the matrix

D. The determinant of the matrix

Solution

1. Step 1: Understand the definition of rank

   The rank of a matrix is the number of linearly independent rows or columns it has.

2. Step 2: Compare with other options

   Options A, B, and D describe different matrix properties, not rank.

3. Final Answer:

   The number of linearly independent rows or columns -> Option A

4. Quick Check:

   Rank = independent directions [OK]

Hint: Rank counts independent rows or columns [OK]

Common Mistakes:

• Confusing rank with matrix size
• Thinking rank is the sum of elements
• Mixing rank with determinant

2. Which MATLAB command correctly computes the null space of a matrix A?

easy

A. rank(A)

B. det(A)

C. null(A)

D. inv(A)

Solution

1. Step 1: Recall MATLAB functions for matrix properties

   null(A) returns the null space vectors of matrix A.

2. Step 2: Identify incorrect options

   rank(A) gives rank, det(A) gives determinant, inv(A) gives inverse if it exists.

3. Final Answer:

   null(A) -> Option C

4. Quick Check:

   null space = null(A) [OK]

Hint: Use null(A) to find null space vectors [OK]

Common Mistakes:

• Using rank(A) instead of null(A)
• Confusing determinant with null space
• Trying to invert a non-square matrix

3. Given the matrix A = [1 2 3; 2 4 6; 3 6 9], what is the output of rank(A) in MATLAB?

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Analyze matrix linear dependence

   Rows 2 and 3 are multiples of row 1, so only 1 row is independent. But row 1 and 2 are linearly dependent, so rank is less than 3.

2. Step 2: Determine rank

   Actually, rows 2 and 3 are multiples of row 1, so rank is 1, but check carefully: row 2 = 2*row 1, row 3 = 3*row 1, so only one independent row.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Rank = 2 for dependent rows [OK]

Hint: Check if rows are multiples to find rank fast [OK]

Common Mistakes:

• Assuming rank equals number of rows
• Ignoring linear dependence
• Confusing rank with matrix size

4. Consider the MATLAB code:

A = [1 2 3; 4 5 6];
N = null(A);
disp(size(N));

What is the correct output of size(N)?

medium

A. [3 1]

B. [3 2]

C. [2 1]

D. [2 3]

Solution

1. Step 1: Determine matrix size and rank

   Matrix A is 2x3. Rank is 2 because rows are independent.

2. Step 2: Calculate null space dimension

   Null space dimension = number of columns - rank = 3 - 2 = 1. So null(A) returns a 3x1 matrix.

3. Final Answer:

   [3 1] -> Option A

4. Quick Check:

   Null space size = columns x (columns - rank) [OK]

Hint: Null space columns = cols - rank [OK]

Common Mistakes:

• Confusing rows and columns in size
• Forgetting null space dimension formula
• Expecting null space to be square

5. You have a matrix B of size 4x5 with rank(B) = 3. Which MATLAB command gives the dimension of the null space of B?

hard

A. size(B, 2) + rank(B)

B. rank(B)

C. size(B, 1) - rank(B)

D. size(null(B), 2)

Solution

1. Step 1: Understand null space dimension

   Null space dimension = number of columns - rank = 5 - 3 = 2.

2. Step 2: Use MATLAB to find null space dimension

   null(B) returns a matrix whose columns form a basis for the null space. The number of columns is the null space dimension. So size(null(B), 2) gives the dimension.

3. Final Answer:

   size(null(B), 2) -> Option D

4. Quick Check:

   Null space dimension = size(null(B), 2) [OK]

Hint: Count columns of null(B) for null space dimension [OK]

Common Mistakes:

• Using rank(B) instead of null space size
• Subtracting rows from rank
• Adding rank and columns incorrectly