Eigenvalues and eigenvectors (eig) in MATLAB - Time & Space Complexity

Time Complexity: Eigenvalues and eigenvectors (eig)

O(n^3)

Understanding Time Complexity

When we find eigenvalues and eigenvectors of a matrix, we want to know how long it takes as the matrix gets bigger.

We ask: 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
[V, D] = eig(A);  % Compute eigenvectors and eigenvalues

This code creates a square matrix and finds its eigenvalues and eigenvectors.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The algorithm internally performs matrix factorizations and iterative procedures.
• How many times: These operations depend on the matrix size n, often involving nested loops over n.

How Execution Grows With Input

As the matrix size n grows, the number of calculations grows quickly because the algorithm works with all rows and columns together.

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 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 if the matrix size doubles, the time to find eigenvalues and eigenvectors increases about eight times.

Common Mistake

[X] Wrong: "Finding eigenvalues is as fast as just scanning the matrix once."

[OK] Correct: The process involves complex calculations that look at all parts of the matrix many times, so it takes much longer than a simple scan.

Interview Connect

Understanding how eigenvalue computations scale helps you explain performance in real projects and shows you know how algorithms behave with bigger data.

Self-Check

"What if we only want eigenvalues but not eigenvectors? How would the time complexity change?"

Practice

1. What does the MATLAB function eig return when applied to a square matrix?

easy

A. Eigenvalues and eigenvectors of the matrix

B. Only the eigenvalues of the matrix

C. Only the eigenvectors of the matrix

D. The inverse of the matrix

Solution

1. Step 1: Understand the purpose of eig

   The eig function in MATLAB is designed to compute eigenvalues and eigenvectors of a square matrix.

2. Step 2: Recall the output of eig

   When called with two output arguments, [V,D] = eig(A), it returns eigenvectors in V and eigenvalues in diagonal matrix D.

3. Final Answer:

   Eigenvalues and eigenvectors of the matrix -> Option A

4. Quick Check:

   eig returns eigenvalues and eigenvectors [OK]

Hint: Remember: eig returns both eigenvalues and eigenvectors [OK]

Common Mistakes:

• Thinking eig returns only eigenvalues
• Confusing eig with inverse function
• Assuming eig returns a scalar

2. Which of the following is the correct syntax to get eigenvalues and eigenvectors of matrix A in MATLAB?

easy

A. [V,D] = eig(A);

B. eig = [V,D](A);

C. V, D = eig(A);

D. eig(A) -> [V,D];

Solution

1. Step 1: Recall MATLAB function call syntax

   In MATLAB, functions return outputs using square brackets for multiple outputs, e.g., [out1, out2] = function(input);.

2. Step 2: Match correct syntax for eig

   The correct way to get eigenvectors V and eigenvalues D is [V,D] = eig(A);.

3. Final Answer:

   [V,D] = eig(A); -> Option A

4. Quick Check:

   Use square brackets for multiple outputs [OK]

Hint: Use square brackets for multiple outputs in MATLAB [OK]

Common Mistakes:

• Using commas instead of brackets for outputs
• Assigning outputs incorrectly
• Using arrow notation which is invalid in MATLAB

3. Given the matrix A = [2 0; 0 3];, what is the output of [V,D] = eig(A); D?

medium

A. [[5 0]; [0 0]]

B. [[3 0]; [0 2]]

C. [[2 0]; [0 3]]

D. [[0 2]; [3 0]]

Solution

1. Step 1: Identify eigenvalues of matrix A

   Matrix A is diagonal with entries 2 and 3, so eigenvalues are 2 and 3.

2. Step 2: Understand output of D from eig

   D is a diagonal matrix with eigenvalues on the diagonal, so D = [2 0; 0 3].

3. Final Answer:

   [[2 0]; [0 3]] -> Option C

4. Quick Check:

   Diagonal matrix D has eigenvalues 2 and 3 [OK]

Hint: Eigenvalues of diagonal matrix are diagonal entries [OK]

Common Mistakes:

• Mixing order of eigenvalues
• Confusing eigenvalues with eigenvectors
• Expecting eigenvalues as a vector instead of diagonal matrix

4. What is wrong with this MATLAB code snippet to get eigenvalues of matrix A?

eigenvalues = eig(A, 'vector');

medium

A. The matrix A must be square and symmetric

B. The variable name eigenvalues is invalid

C. The function eig requires three output arguments

D. The eig function does not accept 'vector' as a second argument

Solution

1. Step 1: Check eig function arguments

   The MATLAB eig function does not take a second argument like 'vector'. It only takes the matrix as input.

2. Step 2: Identify correct usage to get eigenvalues as vector

   To get eigenvalues as a vector, simply call eig(A) without extra arguments.

3. Final Answer:

   The eig function does not accept 'vector' as a second argument -> Option D

4. Quick Check:

   Check function syntax carefully [OK]

Hint: Check MATLAB function syntax in docs before adding arguments [OK]

Common Mistakes:

• Adding unsupported arguments to eig
• Assuming eig returns vector by default without output assignment
• Confusing eig with other functions

5. You have a matrix A = [4 1 0; 1 4 1; 0 1 4];. How can you find the eigenvector corresponding to the largest eigenvalue using MATLAB?

hard

A. largestVec = eig(A);

B. [V,D] = eig(A); [~, idx] = max(diag(D)); largestVec = V(:, idx);

C. [V,D] = eig(A); largestVec = D(:,1);

D. [V,D] = eig(A); largestVec = max(V);

Solution

1. Step 1: Compute eigenvalues and eigenvectors

   Use [V,D] = eig(A); to get eigenvectors V and eigenvalues in diagonal matrix D.

2. Step 2: Find index of largest eigenvalue

   Extract eigenvalues with diag(D), then find index of max eigenvalue with [~, idx] = max(diag(D));.

3. Step 3: Select eigenvector corresponding to largest eigenvalue

   Use index to get eigenvector: largestVec = V(:, idx);.

4. Final Answer:

   [V,D] = eig(A); [~, idx] = max(diag(D)); largestVec = V(:, idx); -> Option B

5. Quick Check:

   Index max eigenvalue, select eigenvector column [OK]

Hint: Use max(diag(D)) to find largest eigenvalue index [OK]

Common Mistakes:

• Using eigenvalues matrix D as vector directly
• Selecting wrong column of eigenvectors
• Confusing eigenvalues with eigenvectors