np.linalg.solve() for linear systems in NumPy - Time & Space Complexity

Time Complexity: np.linalg.solve() for linear systems

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to solve linear equations grows as the size of the system increases.

How does the work change when we have more variables and equations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

# Create a random 3x3 matrix A and vector b
A = np.random.rand(3, 3)
b = np.random.rand(3)

# Solve the system Ax = b
x = np.linalg.solve(A, b)

This code solves a system of 3 linear equations with 3 unknowns using numpy's solver.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix factorization and substitution steps inside the solver.
• How many times: These operations involve nested loops over the matrix size, repeated roughly n times for an n x n matrix.

How Execution Grows With Input

As the number of variables (n) grows, the work to solve the system grows quickly because the solver does many calculations involving all 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: 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 you double the number of variables, the time to solve the system grows about eight times.

Common Mistake

[X] Wrong: "Solving linear systems with np.linalg.solve() takes time proportional to n, so doubling variables doubles time."

[OK] Correct: The solver does many nested calculations involving all variables, so time grows much faster than just doubling.

Interview Connect

Knowing how solving linear systems scales helps you understand performance in data science tasks like regression or simulations.

Self-Check

"What if we used a sparse matrix solver instead of np.linalg.solve()? How would the time complexity change?"

Practice

1. What does np.linalg.solve(A, b) do in NumPy?

easy

A. Solves the system of linear equations Ax = b for x

B. Calculates the determinant of matrix A

C. Finds the inverse of matrix A

D. Multiplies matrix A by vector b

Solution

1. Step 1: Understand the function purpose

   np.linalg.solve() is designed to find the vector x that satisfies the equation Ax = b, where A is a square matrix and b is a vector.

2. Step 2: Differentiate from other matrix operations

   Calculating determinant, inverse, or multiplication are different operations and use other functions like np.linalg.det(), np.linalg.inv(), or @ operator respectively.

3. Final Answer:

   Solves the system of linear equations Ax = b for x -> Option A

4. Quick Check:

   np.linalg.solve() = solve Ax=b [OK]

Hint: It finds x in Ax = b, not determinant or inverse [OK]

Common Mistakes:

• Confusing solve() with matrix inverse
• Using solve() for non-square matrices
• Thinking it multiplies matrices

2. Which of the following is the correct syntax to solve the system Ax = b using NumPy?

easy

A. np.linalg.solve(b, A)

B. np.solve.linalg(A, b)

C. np.linalg.solve(A, b)

D. np.solve(A, b)

Solution

1. Step 1: Recall correct function call

   The correct function is np.linalg.solve() with the first argument as matrix A and second as vector b.

2. Step 2: Check argument order and module

   Arguments must be (A, b), not reversed. The function is inside np.linalg, not np.solve.

3. Final Answer:

   np.linalg.solve(A, b) -> Option C

4. Quick Check:

   Correct syntax = np.linalg.solve(A, b) [OK]

Hint: Remember: np.linalg.solve(matrix, vector) [OK]

Common Mistakes:

• Swapping A and b arguments
• Using wrong module or function name
• Missing np.linalg prefix

3. What is the output of this code?

import numpy as np
A = np.array([[2, 1], [1, 3]])
b = np.array([10, 15])
x = np.linalg.solve(A, b)
print(x)

medium

A. [2. 5.]

B. [4. 3.]

C. [5. 2.]

D. [3. 4.]

Solution

1. Step 1: Set up equations from matrix and vector

   Matrix A and vector b represent:
   2x + 1y = 10
   1x + 3y = 15

2. Step 2: Solve equations manually or trust np.linalg.solve

   Solving:
   From first: y = (10 - 2x)
   Substitute in second: x + 3(10 - 2x) = 15
   x + 30 - 6x = 15
   -5x = -15
   x = 3
   y = 10 - 2*3 = 4
   np.linalg.solve gives x = [3. 4.]

3. Final Answer:

   [3. 4.] -> Option D

4. Quick Check:

   np.linalg.solve(A,b) = [3. 4.] [OK]

Hint: Use np.linalg.solve to get exact solution vector [OK]

Common Mistakes:

• Mixing up order of variables in solution
• Incorrect manual calculation
• Confusing rows and columns in matrix

4. What error will this code produce?

import numpy as np
A = np.array([[1, 2], [3, 4], [5, 6]])
b = np.array([7, 8])
x = np.linalg.solve(A, b)

medium

A. ValueError: shapes (3,2) and (2,) not aligned

B. LinAlgError: Last 2 dimensions of the array must be square

C. TypeError: unsupported operand type(s)

D. No error, returns solution vector

Solution

1. Step 1: Check matrix shape requirements

   Matrix A must be square (same number of rows and columns) to use np.linalg.solve(). Here, A is 3x2, not square.

2. Step 2: Identify error raised by NumPy

   NumPy raises LinAlgError with message about last 2 dimensions needing to be square.

3. Final Answer:

   LinAlgError: Last 2 dimensions of the array must be square -> Option B

4. Quick Check:

   Non-square A causes LinAlgError [OK]

Hint: Matrix A must be square for np.linalg.solve() [OK]

Common Mistakes:

• Using non-square matrix A
• Expecting multiplication instead of solve
• Ignoring error message details

5. You have the system:

3x + 2y - z = 1
2x - 2y + 4z = -2
-x + 0.5y - z = 0

Which code correctly solves for x, y, z using np.linalg.solve()?

hard

A. A = np.array([[3, 2, -1], [2, -2, 4], [-1, 0.5, -1]])
b = np.array([1, -2, 0])
x = np.linalg.solve(A, b)

B. A = np.array([[3, 2, 1], [2, -2, 4], [-1, 0.5, -1]])
b = np.array([1, -2, 0])
x = np.linalg.solve(A, b)

C. A = np.array([[3, 2, -1], [2, -2, 4], [-1, 0.5, -1]])
b = np.array([1, 2, 0])
x = np.linalg.solve(A, b)

D. A = np.array([[3, 2, -1], [2, -2, 4], [-1, 0.5, -1]])
b = np.array([1, -2, 0])
x = np.linalg.inv(A) @ b

Solution

1. Step 1: Translate system to matrix and vector

   Coefficients matrix A must match the system exactly:
   Row 1: 3, 2, -1
   Row 2: 2, -2, 4
   Row 3: -1, 0.5, -1
   Constants vector b is [1, -2, 0].

2. Step 2: Check each option for correctness

   A = np.array([[3, 2, -1], [2, -2, 4], [-1, 0.5, -1]]) b = np.array([1, -2, 0]) x = np.linalg.solve(A, b) matches coefficients and constants exactly.
   A = np.array([[3, 2, 1], [2, -2, 4], [-1, 0.5, -1]]) b = np.array([1, -2, 0]) x = np.linalg.solve(A, b) has wrong sign in third element of first row.
   A = np.array([[3, 2, -1], [2, -2, 4], [-1, 0.5, -1]]) b = np.array([1, 2, 0]) x = np.linalg.solve(A, b) has wrong second element in b.
   A = np.array([[3, 2, -1], [2, -2, 4], [-1, 0.5, -1]]) b = np.array([1, -2, 0]) x = np.linalg.inv(A) @ b uses inverse multiplication which is less efficient and not recommended.

3. Final Answer:

   Option A code correctly solves the system -> Option A

4. Quick Check:

   Correct matrix and vector with np.linalg.solve() [OK]

Hint: Match coefficients and constants exactly; use np.linalg.solve() [OK]

Common Mistakes:

• Wrong signs in matrix or vector
• Using inverse instead of solve()
• Mixing up constants vector values