Solve Linear System

Background Knowledge

A linear system $Ax = b$ represents $n$ equations with $n$ unknowns, where $A$ is an $n \times n$ coefficient matrix, $x$ is the unknown solution vector, and $b$ is the right-hand side vector. Matrix-vector multiplication $A @ x$ computes the linear combination of columns of $A$ weighted by components of $x$. For the system to have a unique solution, $A$ must be square and invertible (non-singular, with non-zero determinant and full rank).

NumPy provides efficient tools for solving these systems. The function np.linalg.solve(A, b) uses LU decomposition (or similar direct methods) to compute $x = A^{-1}b$ stably and efficiently, avoiding explicit matrix inversion which is numerically unstable and $O(n^3)$ more costly. In contrast, np.linalg.inv(A) @ b computes the full inverse first, which is less recommended for large or ill-conditioned matrices. Verification checks if $\|A @ x - b\|$ is small (e.g., via tolerance), accounting for floating-point precision.

Algorithm/Approach

Use direct solver np.linalg.solve(A, b) for the primary solution, as it's optimized for dense matrices and handles conditioning better than inversion. Compute verification by forward-substituting the solution back: $A @ x$, then compare element-wise to $b$ within a tolerance (e.g., $10^{-10}$). Return results in rounded lists for the specified format, ensuring numerical stability by avoiding unnecessary operations like inversion.

Step-by-Step Strategy

1. Validate inputs: Ensure A is square ($A.shape == A.shape$) and compatible with b ($A.shape == b.shape$); raise error if not.
2. Solve the system: Call x = np.linalg.solve(A, b) to get the exact solution vector.
3. Verify solution: Compute verification = A @ x and check if np.allclose(verification, b, atol=1e-10) for is_correct.
4. Format output: Round x and verification to 2 decimals using np.round(..., 2).tolist(), then pack into dictionary {'solution':..., 'verification':..., 'is_correct':...}.

Common Pitfalls

• Non-square or singular matrices: np.linalg.solve raises LinAlgError if $A$ is singular (det$A$=0) or mismatched shapes—handle with try-except or checks.
• Ill-conditioned matrices: Near-singular $A$ (high condition number $\kappa(A) = \|A\| \cdot \|A^{-1}\|$) amplifies errors; use np.linalg.cond(A) to diagnose, but solver is robust for most cases.
• Rounding precision: Use np.round after computation, not before, to avoid distorting verification; lists must be flat (not arrays).
• Floating-point tolerance: Hardcode small atol for is_correct; exact equality fails due to precision (e.g., 5.0000000001 != 5.0).
• Import oversight: Ensure import numpy as np; forget @ operator (use np.dot as fallback).

Time & Space Complexity

• Time: $O(n^3)$ dominant from np.linalg.solve (LU decomposition) and $A @ x$ ($O(n^2)$); negligible for verification/formatting. Suitable for $n \leq 10^3$.
• Space: $O(n^2)$ for $A$, $O(n)$ for vectors; temporary $O(n^2)$ in solver—efficient for dense matrices.