Linear systems are the basic computational problem in scientific computing. Even when the original problem is nonlinear, algorithms often reduce it to a sequence of linear systems by linearizing the problem near the current estimate.
A matrix equation \(\bA\bx=\bb\) asks whether the data vector \(\bb\) can be produced by combining the columns of \(\bA\). The unknown vector \(\bx\) contains the weights in that combination. Existence, uniqueness, and numerical difficulty are all controlled by the geometry of those columns.
Linear Systems
A linear system is a collection of linear equations involving the same set of variables. In matrix-vector notation, we package these equations into a single compact form that is amenable to both theoretical analysis and high-performance computation.
The matrix-vector form of a linear system is \(\bA\bx = \bb\), where:
\(\bA \in \fR^{m \times n}\) is the coefficient matrix representing the system’s structure.
\(\bx \in \fR^n\) is the vector of unknown variables we wish to determine.
\(\bb \in \fR^m\) is the right-hand side vector, often representing observed data or a source term.
(Shape discipline) If \(\bA \in \fR^{m\times n}\), then \(\bx\) must have \(n\) entries and \(\bb\) must have \(m\) entries. The number of columns is the number of unknowns. The number of rows is the number of equations or measurements.
(Two equations) The system \[
\begin{align}
x + 2y = 3, \qquad 3x-y = 1
\end{align}
\] can be written as \[
\begin{align}
\begin{pmatrix}1&2\\3&-1\end{pmatrix}
\begin{pmatrix}x\\y\end{pmatrix}
=
\begin{pmatrix}3\\1\end{pmatrix}.
\end{align}
\] The first row encodes the first equation; the second row encodes the second equation.
Convert \(\{x + 2y = 3,\; 3x - y = 1\}\) to the form in the result above.
Check the dimensions of \(\bA\), \(\bx\), and \(\bb\) before solving. Which part of the result above determines each shape?
Solve in NumPy via np.linalg.solve(A, b). Verify with the residual from the result above.
Rows, Columns, and Geometry
There are two complementary ways to read \(\bA\bx=\bb\).
Row view: Each row is one linear equation. In two or three dimensions, each equation describes a line, plane, or hyperplane. Solving the system means finding their intersection.
Column view: The product \(\bA\bx\) is a weighted sum of the columns of \(\bA\). Solving the system means expressing \(\bb\) as a linear combination of those columns.
(The Column Perspective) If \(\bA=[\ba_1,\ba_2,...,\ba_n]\), then \[
\begin{align}
\bA\bx = x_1 \ba_1 + x_2 \ba_2 + ... + x_n \ba_n.
\end{align}
\] The system \(\bA\bx = \bb\) is consistent exactly when \(\bb\) lies in the span of the columns of \(\bA\).
If \(\bA\bx_1 = \bb_1\) and \(\bA\bx_2 = \bb_2\), then for any scalars \(\alpha, \beta\): \[
\begin{align}
\bA(\alpha\bx_1 + \beta\bx_2) = \alpha\bb_1 + \beta\bb_2.
\end{align}
\] Implication: Solutions to \(\bA\bx = \bb\) can be decomposed and recombined linearly.
Use the result above to solve \(\bA\bx = 3\bb_1 - 2\bb_2\) given only the solutions \(\bx_1, \bx_2\) for \(\bb_1, \bb_2\).
How does np.linalg.solve(A, B) for a matrix \(\bB\) exploit this?
Invertibility and Existence
For square systems (\(\bA \in \fR^{n \times n}\)), the most critical question is whether a unique solution exists for any given right-hand side. This property is known as invertibility or nonsingularity.
For rectangular systems, the same questions still matter but the answer changes.
Square: \(m=n\). A unique solution may exist.
Overdetermined: \(m>n\). There are more equations than unknowns; usually no exact solution exists, so we solve a least squares problem.
Underdetermined: \(m<n\). There are fewer equations than unknowns; if a solution exists, it is usually not unique.
The following are equivalent for \(\bA \in \fR^{n \times n}\):
\(\bA\) is invertible (\(\det(\bA) \neq 0\)).
\(\bA\bx = \bb\) has a unique solution for every \(\bb\).
\(\bA\bx = \bzero\) has only the trivial solution (\(\bx = \bzero\)).
\(\text{rank}(\bA) = n\) (Full Rank).
Columns of \(\bA\) are linearly independent.
(Determinants are not algorithms) The determinant is useful theoretically, but numerical codes do not test invertibility by computing \(\det(\bA)\). Rank, singular values, and condition numbers are more informative and more stable.
Determine invertibility using the result above: \(\bA = \begin{pmatrix} 2 & -1 \\ 4 & -2 \end{pmatrix}\), \(\bB = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}\).
Check consistency of \(\bA = \begin{pmatrix}1&2\\3&6\end{pmatrix}, \bb = \begin{pmatrix}1\\4\end{pmatrix}\) using the column perspective in the result above and np.linalg.matrix\_rank.
Residuals and Approximate Solutions
For an approximate solution \(\hat{\bx}\) to \(\bA\bx=\bb\), the residual is \[
\begin{align}
\br = \bb-\bA\hat{\bx}.
\end{align}
\] It measures how well \(\hat{\bx}\) satisfies the equations.
(Residual vs. error) The error is \(\hat{\bx}-\bx^*\), where \(\bx^*\) is the exact solution. The residual is computable; the error usually is not. A small residual means the equations are nearly satisfied, but it does not always mean the solution is accurate. Ill-conditioned matrices can turn small residuals into large errors.
(Inconsistent system) The equations \[
\begin{align}
x+y=1, \qquad x+y=3
\end{align}
\] cannot both be true. In matrix form, \(\bb\) is not in the column space of \(\bA\). The best we can do is choose \(\hat{\bx}\) so that the residual \(\bb-\bA\hat{\bx}\) is small in a chosen norm. This is the least squares problem.
Linear Combinations and Bases
Vectors \(\{\bx_1, ..., \bx_k\}\) are independent if \(\sum \alpha_i \bx_i = \bzero \Rightarrow \alpha_i = 0\) for all \(i\).
A linearly independent set that spans the space. The number of vectors in any basis is the dimension.
Rank
The rank of a matrix is the number of independent directions its columns span. It measures how many genuinely different constraints or directions are present after removing redundancy.
The rank, \(\text{rank}(\bA)\), is the dimension of the column space. It is always true that \(\text{rank}(\bA) \leq \min(m, n)\).
Full Rank: The matrix has the maximum possible rank, \(\text{rank}(\bA) = \min(m, n)\).
Rank Deficient (Singular): A square matrix with \(\text{rank}(\bA) < n\). Such systems do not have unique solutions.
(Rank and solution structure) For \(\bA\in\fR^{m\times n}\):
Full column rank (\(\text{rank}(\bA)=n\)) means the columns are independent.
Full row rank (\(\text{rank}(\bA)=m\)) means the rows are independent.
Rank deficiency means there is redundancy: some row or column information can be produced from the rest.
(Numerical Rank) In code, do not use exact row-reduction to find rank; it is numerically unstable. Use np.linalg.matrix\_rank, which estimates rank from the singular values. A matrix can be mathematically full rank but numerically rank deficient if one singular value is tiny compared to the others.
For \(\bA \in \fR^{m \times n}\): \(\text{rank}(\bA) + \text{nullity}(\bA) = n\).
- Nullity: Dimension of the null space \(\{\bx : \bA\bx = \bzero\}\).
(General solution form) If \(\bA\bx=\bb\) is consistent and \(\bx_p\) is one particular solution, then every solution has the form \[
\begin{align}
\bx = \bx_p + \bz, \qquad \bz \in \mathcal{N}(\bA).
\end{align}
\] The null space contains the directions you can add without changing \(\bA\bx\).
Use the result above to explain why a ``wide’’ matrix (\(m<n\)) must have a non-trivial null space.
Find the general solution to a consistent \(2 \times 3\) system in the form \(\bx=\bx_p+\bz\), where \(\bz\in\mathcal{N}(\bA)\).
Check directly that adding a null-space vector leaves \(\bA\bx\) unchanged.
The Four Fundamental Subspaces
The structure of any linear operator \(\bA \in \fR^{m \times n}\) with rank \(r\) is completely characterized by four subspaces. Understanding these spaces is essential for solving least squares problems and understanding the behavior of iterative solvers.
\(\fR^m, \dim=r\). Span of columns.
\(\fR^n, \dim=n-r\). Solutions to \(\bA\bx = \bzero\).
\(\fR^n, \dim=r\). Span of rows.
\(\fR^m, \dim=m-r\). Solutions to \(\bA^T\by = \bzero\).
Solvability: \(\bA\bx = \bb\) has a solution iff \(\bb \in \mathcal{R}(\bA)\), i.e., \(\bb \perp \mathcal{N}(\bA^T)\).
For \(\bA = \begin{pmatrix}1&2&3\\2&4&6\end{pmatrix}\), use the result above and the result above to find dimensions and bases for all four spaces.
Verify the two orthogonality statements in the result above.
Verify \(\bb = (1, 3)^T\) is not in the column space. What is the projection of \(\bb\) onto \(\mathcal{R}(\bA)\)?