Systems of Linear Equations: The Kronecker–Capelli Theorem

The Fundamental Problem of Linear Algebra

The system Ax = b (m equations, n unknowns) is the central problem of computational and theoretical mathematics. When is the system consistent? How many solutions does it have? How can they be found?

Gaussian Method

We reduce the augmented matrix [A|b] to row-echelon form using elementary row operations. Row-echelon form: in each nonzero row, the leading entry stands further to the right than in the previous row.

Reduced row-echelon form (Gauss–Jordan): the leading entry in each row equals 1, and in its column there are zeros above and below.

Kronecker–Capelli Theorem

The system Ax = b is consistent (has at least one solution) if and only if rank(A) = rank(A|b).

Three cases:

1. rank A = rank(A|b) = n: a unique solution
2. rank A = rank(A|b) = r < n: infinitely many solutions (n−r degrees of freedom)
3. rank A < rank(A|b): inconsistent (no solutions)

Structure of the General Solution

If the system is consistent, the general solution: x = x* + xₒ, where x* is a particular solution, xₒ is the general solution of the homogeneous system Ax = 0.

The set of solutions of the homogeneous system is the kernel (null-space) of matrix A, a linear subspace of dimension n − rank A.

Rank Theorem: rank A + dim(ker A) = n (for A: m×n).

LU Decomposition Method

An efficient algorithm for computations: A = LU, where L is lower triangular with ones on the diagonal, U is upper triangular. The Gaussian method is essentially LU decomposition.

To solve Ax = b: Ly = b (forward substitution), Ux = y (backward substitution). Complexity is O(n³) for computing the decomposition, O(n²) for solving when the decomposition is known.

LU decomposition with partial pivoting (selection of the leading element) is the computational mathematics standard (LAPACK library).