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

Time Complexity: Eigenvalues and eigenvectors (eig)

O(n^3)

Understanding Time Complexity

We want to understand how the time to find eigenvalues and eigenvectors changes as the matrix size grows.

How does the work increase when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.linalg import eig

n = 10  # Example size
A = np.random.rand(n, n)  # Create a random n x n matrix
values, vectors = eig(A)  # Compute eigenvalues and eigenvectors
    

This code creates a square matrix and computes its eigenvalues and eigenvectors using scipy.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Internal matrix factorizations and transformations to find eigenvalues and eigenvectors.
• How many times: These operations involve multiple passes over the n x n matrix, roughly proportional to n cubed steps.

How Execution Grows With Input

As the matrix size n grows, the work needed grows much faster than n or n squared.

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 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 find eigenvalues and eigenvectors grows roughly with the cube of the matrix size.

Common Mistake

[X] Wrong: "Finding eigenvalues is as fast as simple loops over the matrix, like O(n^2)."

[OK] Correct: The process involves complex matrix operations that require more work than just looking at each element once.

Interview Connect

Knowing how eigenvalue computations scale helps you understand performance in data science tasks like PCA or stability analysis.

Self-Check

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

Practice

1. What do eigenvalues represent in the context of a matrix transformation?

easy

A. The sum of all matrix elements

B. The directions that change completely under the matrix

C. How much eigenvectors stretch or shrink when the matrix is applied

D. The inverse of the matrix

Solution

1. Step 1: Understand eigenvalues meaning

   Eigenvalues measure the factor by which eigenvectors are stretched or shrunk when multiplied by the matrix.

2. Step 2: Compare options with definition

   How much eigenvectors stretch or shrink when the matrix is applied correctly describes this stretching/shrinking effect. Other options describe unrelated concepts.

3. Final Answer:

   How much eigenvectors stretch or shrink when the matrix is applied -> Option C

4. Quick Check:

   Eigenvalues = stretch/shrink factor [OK]

Hint: Eigenvalues tell how vectors scale under the matrix [OK]

Common Mistakes:

• Confusing eigenvalues with eigenvectors
• Thinking eigenvalues are directions
• Mixing eigenvalues with matrix sum

2. Which of the following is the correct way to import the function to compute eigenvalues and eigenvectors using scipy?

easy

A. from scipy.linalg import eig

B. import scipy.eigen as eig

C. from scipy.linalg import eigenvalues

D. import scipy.linalg.eig as eigen

Solution

1. Step 1: Recall scipy function for eigenvalues

   The function to compute eigenvalues and eigenvectors is named 'eig' and is in scipy.linalg.

2. Step 2: Check import syntax

   from scipy.linalg import eig correctly imports 'eig' from 'scipy.linalg'. Other options use incorrect module names or syntax.

3. Final Answer:

   from scipy.linalg import eig -> Option A

4. Quick Check:

   Correct import = from scipy.linalg import eig [OK]

Hint: Use 'from scipy.linalg import eig' to get eigenvalues [OK]

Common Mistakes:

• Using wrong module names like scipy.eigen
• Trying to import non-existent functions
• Incorrect import syntax

3. What is the output of the following code?

import numpy as np
from scipy.linalg import eig
A = np.array([[2, 0], [0, 3]])
values, vectors = eig(A)
print(values)

medium

A. [2.+0.j 3.+0.j]

B. [0.+2.j 0.+3.j]

C. [5.+0.j 0.+0.j]

D. [2 3]

Solution

1. Step 1: Understand matrix and eig function

   Matrix A is diagonal with values 2 and 3 on the diagonal. Eigenvalues of a diagonal matrix are the diagonal elements.

2. Step 2: Predict output of eig

   scipy.linalg.eig returns eigenvalues as complex numbers, so output will be [2.+0.j 3.+0.j].

3. Final Answer:

   [2.+0.j 3.+0.j] -> Option A

4. Quick Check:

   Diagonal matrix eigenvalues = diagonal elements [OK]

Hint: Diagonal matrix eigenvalues = diagonal entries as complex numbers [OK]

Common Mistakes:

• Expecting real numbers instead of complex
• Adding eigenvalues instead of listing
• Confusing eigenvalues with eigenvectors

4. The following code throws an error. What is the main issue?

import numpy as np
from scipy.linalg import eig
A = np.array([[1, 2, 3], [4, 5, 6]])
values, vectors = eig(A)

medium

A. eig function is misspelled

B. Matrix A is not square

C. Missing import for numpy

D. Vectors variable name is invalid

Solution

1. Step 1: Check matrix shape

   Matrix A has shape (2, 3), which is not square (rows != columns).

2. Step 2: Understand eig requirements

   scipy.linalg.eig requires a square matrix to compute eigenvalues and eigenvectors.

3. Final Answer:

   Matrix A is not square -> Option B

4. Quick Check:

   eig needs square matrix [OK]

Hint: Check matrix shape; eig needs square matrix [OK]

Common Mistakes:

• Ignoring matrix shape requirement
• Assuming eig works on any matrix
• Blaming variable names or imports

5. Given the matrix B = [[4, 1], [2, 3]], which of the following is a correct eigenvalue computed using scipy.linalg.eig?

hard

A. 7.0 + 0.j

B. 3.0 + 0.j

C. 1.0 + 0.j

D. 5.0 + 0.j

Solution

1. Step 1: Calculate eigenvalues of B

   Eigenvalues satisfy det(B - λI) = 0. For B=[[4,1],[2,3]], characteristic polynomial is (4-λ)(3-λ)-2=0 -> λ² -7λ +10=0.

2. Step 2: Solve quadratic equation

   Roots are λ = (7 ± sqrt(49 - 40))/2 = (7 ± 3)/2 -> λ=5 or λ=2.

3. Step 3: Match options

   5.0 + 0.j is 5.0 + 0.j, which matches one eigenvalue. Others do not match.

4. Final Answer:

   5.0 + 0.j -> Option D

5. Quick Check:

   Eigenvalues = 5 and 2 [OK]

Hint: Solve characteristic polynomial for eigenvalues [OK]

Common Mistakes:

• Miscomputing characteristic polynomial
• Ignoring complex number format
• Choosing wrong root from quadratic