Linear systems are characterized by the properties of additivity and homogeneity, which allow for the decomposition of complex operators into simpler components.
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.
Convert \(\{x + 2y = 3,\; 3x - y = 1\}\) to \(\bA\bx = \bb\).
Solve in NumPy via np.linalg.solve(A, b). Verify with np.linalg.norm(b - A @ x).
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.
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.
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.
Determine invertibility: \(\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}\) via np.linalg.matrix\_rank.
Linear Combinations and Bases
The Column Perspective. While we often think of \(\bA\bx = \bb\) as a set of row equations, it is often more powerful to view it as a statement about columns. The product \(\bA\bx\) is a linear combination of the columns of \(\bA\) weighted by the entries of \(\bx\): \[
\begin{align}
\bA\bx = x_1 \ba_1 + x_2 \ba_2 + ... + x_n \ba_n.
\end{align}
\] The system \(\bA\bx = \bb\) asks a fundamental geometric question: ``Can the vector \(\bb\) be represented as a weighted sum of the columns of \(\bA\)?’’ If the answer is yes, the system is consistent.
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 a measure of its “information content,” representing the number of independent directions it can span.
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.
Numerical Rank. In code, never use row-reduction to find rank; it is numerically unstable. Use np.linalg.matrix\_rank, which uses the Singular Value Decomposition (SVD).
For \(\bA \in \fR^{m \times n}\): \(\text{rank}(\bA) + \text{nullity}(\bA) = n\).
- Nullity: Dimension of the null space \(\{\bx : \bA\bx = \bzero\}\).
Find the general solution to a \(2 \times 3\) system as \(\bx = \bx_p + \bx_n\) (particular + null space).
Why must a ``wide’’ matrix (\(m < n\)) have a non-trivial null space?
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}\), find dimensions and bases for all four spaces.
Verify \(\bb = (1, 3)^T\) is not in the column space. What is the projection of \(\bb\) onto \(\mathcal{R}(\bA)\)?