np.linalg.eig() for eigenvalues in NumPy - Time & Space Complexity

Time Complexity: np.linalg.eig() for eigenvalues

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to find eigenvalues grows as the matrix size increases.

How does the work change when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

A = np.random.rand(n, n)
w, v = np.linalg.eig(A)

This code creates a square matrix of size n by n and computes its eigenvalues and eigenvectors.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix factorization and iterative calculations inside the eigenvalue algorithm.
• How many times: These operations involve multiple passes over the n by n matrix, roughly proportional to n cubed or more.

How Execution Grows With Input

As the matrix size n grows, the work needed grows quickly because the algorithm handles all rows and columns multiple times.

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 tripling n makes the work about 27 times bigger.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to find eigenvalues grows roughly with the cube of the matrix size, so bigger matrices take much more time.

Common Mistake

[X] Wrong: "Finding eigenvalues is a quick operation that grows linearly with matrix size."

[OK] Correct: The process involves complex matrix operations that touch many elements multiple times, so it grows much faster than linear.

Interview Connect

Knowing how eigenvalue calculations scale helps you understand performance in data science tasks like PCA or spectral clustering, showing you can think about algorithm costs clearly.

Self-Check

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

Practice

1. What does the function np.linalg.eig() return when applied to a square matrix?

easy

A. The determinant and inverse of the matrix

B. An array of eigenvalues and a matrix of eigenvectors

C. The transpose and trace of the matrix

D. The sum and product of matrix elements

Solution

1. Step 1: Understand the purpose of np.linalg.eig()

   This function is designed to find eigenvalues and eigenvectors of a square matrix.

2. Step 2: Recall the output format

   It returns two objects: one array with eigenvalues and one matrix with eigenvectors as columns.

3. Final Answer:

   An array of eigenvalues and a matrix of eigenvectors -> Option B

4. Quick Check:

   Eigenvalues and eigenvectors [OK]

Hint: Remember: eig() returns eigenvalues and eigenvectors [OK]

Common Mistakes:

• Confusing eigenvalues with determinant
• Expecting only one output instead of two
• Mixing eigenvectors with matrix transpose

2. Which of the following is the correct syntax to compute eigenvalues and eigenvectors of matrix A using NumPy?

easy

A. eigenvalues, eigenvectors = np.linalg.eig(A)

B. eigenvalues = np.linalg.eigvals(A)

C. eigenvectors, eigenvalues = np.linalg.eig(A)

D. eigenvalues, eigenvectors = np.eig.linalg(A)

Solution

1. Step 1: Recall the correct function and output order

   The function np.linalg.eig() returns eigenvalues first, then eigenvectors.

2. Step 2: Check syntax correctness

   eigenvalues, eigenvectors = np.linalg.eig(A) correctly assigns eigenvalues and eigenvectors in order from np.linalg.eig(A).

3. Final Answer:

   eigenvalues, eigenvectors = np.linalg.eig(A) -> Option A

4. Quick Check:

   Correct function and order [OK]

Hint: eig() returns (values, vectors) in that order [OK]

Common Mistakes:

• Swapping eigenvalues and eigenvectors in assignment
• Using wrong function like np.linalg.eigvals() for both outputs
• Incorrect module or function name

3. Given the matrix A = np.array([[2, 0], [0, 3]]), what will be the output of np.linalg.eig(A)[0]?

medium

A. [3. 2.]

B. [0. 0.]

C. [2. 3.]

D. [5. 0.]

Solution

1. Step 1: Identify eigenvalues of a diagonal matrix

   For a diagonal matrix, eigenvalues are the diagonal elements: 2 and 3.

2. Step 2: Check the output of np.linalg.eig(A)[0]

   This returns the eigenvalues array, which will be [2. 3.].

3. Final Answer:

   [2. 3.] -> Option C

4. Quick Check:

   Diagonal elements = eigenvalues [OK]

Hint: Diagonal matrix eigenvalues = diagonal elements [OK]

Common Mistakes:

• Confusing eigenvalues order
• Expecting eigenvectors instead of eigenvalues
• Misreading matrix elements

4. What is wrong with this code snippet?

import numpy as np
A = np.array([[1, 2], [3, 4]])
eigenvalues, eigenvectors = np.linalg.eigvals(A)

medium

A. np.linalg.eigvals() returns only eigenvalues, not eigenvectors

B. Matrix A is not square

C. np.linalg.eigvals() requires two arguments

D. The import statement is incorrect

Solution

1. Step 1: Understand the function np.linalg.eigvals()

   This function returns only eigenvalues, not eigenvectors.

2. Step 2: Check the assignment in the code

   The code tries to unpack two values, but eigvals() returns only one, causing an error.

3. Final Answer:

   np.linalg.eigvals() returns only eigenvalues, not eigenvectors -> Option A

4. Quick Check:

   eigvals() returns one output [OK]

Hint: eigvals() returns only eigenvalues, not vectors [OK]

Common Mistakes:

• Expecting two outputs from eigvals()
• Thinking matrix must be non-square
• Misunderstanding import syntax

5. You have a matrix B = np.array([[1, 0], [0, -3]]). You want to find the eigenvalue with the largest magnitude. Which code snippet correctly finds it?

hard

A. vals, vecs = np.linalg.eig(B)
largest = max(vecs)

B. vals = np.linalg.eigvals(B)
largest = max(vals)

C. vals = np.linalg.eigvals(B)
largest = vals[np.argmax(vals)]

D. vals, vecs = np.linalg.eig(B)
largest = vals[np.argmax(np.abs(vals))]

Solution

1. Step 1: Compute eigenvalues and eigenvectors

   Use np.linalg.eig(B) to get both eigenvalues and eigenvectors.

2. Step 2: Find eigenvalue with largest magnitude

   Use np.abs(vals) to get absolute values, then np.argmax() to find index of largest magnitude eigenvalue.

3. Step 3: Select eigenvalue at that index

   Indexing vals with that index gives the eigenvalue with largest magnitude.

4. Final Answer:

   vals, vecs = np.linalg.eig(B) largest = vals[np.argmax(np.abs(vals))] -> Option D

5. Quick Check:

   Use abs and argmax on eigenvalues [OK]

Hint: Use np.abs() and np.argmax() on eigenvalues to find largest [OK]

Common Mistakes:

• Using max() directly without abs()
• Trying to find max of eigenvectors
• Using wrong function for eigenvalues