Matrix Theory and the Structure of Linear Systems

Matrices are not merely rectangular arrays of scalars; they are the canonical representations of linear transformations between finite-dimensional vector spaces. Let $V$ and $W$ be vector spaces over a field $\mathbb{F}$ (typically $\mathbb{R}$ or $\mathbb{C}$) with $\dim (V)=n$ and $\dim (W)=m$. Given bases ${\mathcal{B}}_V$ and ${\mathcal{B}}_W$, any linear map $T:V\to W$ corresponds uniquely to a matrix $A\in M_{m,n}(\mathbb{F})$.

1. Matrix Algebra and Non-Commutativity

Matrix multiplication is defined to correspond to the composition of linear maps. For $A\in M_{m,p}(\mathbb{F})$ and $B\in M_{p,n}(\mathbb{F})$, the product $C=AB\in M_{m,n}(\mathbb{F})$ is defined by: $C_{ij}={\sum }_{k=1}^p{A}_{ik}{B}_{kj}$ A critical property of matrix algebra is its non-commutativity: in general, $AB\ne BA$, even for square matrices. This reflects the fact that the order of performing linear transformations matters (e.g., a rotation followed by a shear is not the same as a shear followed by a rotation).

Transposition and Adjoint

The transpose $A^T$ is defined by $(A^T{)}_{ij}=A_{ji}$. An essential identity in matrix algebra is the reversal of order under transposition: $(AB{)}^T=B^T{A}^T$ Proof Sketch: The $(i,j)$-entry of $(AB{)}^T$ is the $(j,i)$-entry of $AB$, which is ${\sum }_k{A}_{jk}{B}_{ki}$. The $(i,j)$-entry of $B^T{A}^T$ is ${\sum }_k(B^T{)}_{ik}(A^T{)}_{kj}={\sum }_k{B}_{ki}{A}_{jk}$, which is identical.

2. Theory of Determinants

The determinant is a functional $\det :M_{n,n}(\mathbb{F})\to \mathbb{F}$ that characterizes the scaling factor of the $n$-dimensional volume under the transformation. Rigorously, it is the unique alternating multilinear form on the columns of $A$ such that $\det (I)=1$.

The Leibniz Formula

For a matrix $A\in M_{n,n}(\mathbb{F})$, the determinant is given by: $\det (A)={\sum }_{\sigma \in S_n}\text{sgn}(\sigma ){\prod }_{i=1}^n{A}_{i,\sigma (i)}$ where $S_n$ is the symmetric group of all permutations of $\{1,\dots ,n\}$, and $\text{sgn}(\sigma )$ is the signature of the permutation (either $+1$ or $-1$).

Key Properties

1. Linearity: The determinant is a linear function of any single row (or column) when others are held fixed.
2. Alternating: Switching any two rows multiplies the determinant by $-1$.
3. Singularity: $\det (A)=0$ if and only if $A$ is singular (non-invertible), which occurs if the rows are linearly dependent.
4. Multiplicativity: $\det (AB)=\det (A)\det (B)$.

3. Matrix Inversion and the Adjugate

A square matrix $A$ is invertible if there exists $A^{-1}$ such that $A{A}^{-1}=A^{-1}A=I$. The existence of $A^{-1}$ is guaranteed if and only if $\det (A)\ne 0$.

The Adjugate Matrix $\text{adj}(A)$ is the transpose of the cofactor matrix $C$, where $C_{ij}=(-1{)}^{i+j}{M}_{ij}$ ($M_{ij}$ being the minor). The relationship is: $A\cdot \text{adj}(A)=\det (A)I⟹A^{-1}=\frac{1}{\det (A)}\text{adj}(A)$ While computationally expensive for large $n$, this formula provides profound theoretical insights into the continuity of the inverse as a function of the matrix entries.

4. Systems of Linear Equations

Consider the system $Ax=b$, where $A\in M_{m,n}$, $x\in {\mathbb{F}}^n$, and $b\in {\mathbb{F}}^m$.

The Rouché–Capelli Theorem

The system $Ax=b$ is consistent (has at least one solution) if and only if the rank of the coefficient matrix $A$ is equal to the rank of the augmented matrix $[A|b]$: $\text{rank}(A)=\text{rank}([A|b])$

• If $\text{rank}(A)=\text{rank}([A|b])=n$, the system has a unique solution.
• If $\text{rank}(A)=\text{rank}([A|b])<n$, the system has infinitely many solutions (assuming an infinite field).

5. Rank-Nullity and Subspaces

The structure of a matrix $A\in M_{m,n}$ is defined by four fundamental subspaces:

1. Column Space $C(A)$: The span of the columns of $A$ (image of the map).
2. Null Space $N(A)$: The set of all $x$ such that $Ax=0$ (kernel).
3. Row Space $C(A^T)$: The span of the rows.
4. Left Null Space $N(A^T)$: The set of all $y$ such that $A^{T}y=0$.

The Rank-Nullity Theorem

For any matrix $A\in M_{m,n}$: $\text{rank}(A)+\dim (N(A))=n$ This theorem bridges the dimension of the input space with the dimensions of the image and the kernel. Note that row rank always equals column rank, even for non-square matrices.

6. Matrix Decompositions

Numerical linear algebra relies on decomposing matrices into simpler forms to facilitate computation.

LU Decomposition

A matrix $A$ (often after row permutations $P$) is factored as $PA=LU$, where $L$ is lower triangular and $U$ is upper triangular. This allows solving $Ax=b$ via two stages of back-substitution: $Ly=Pb$ and $Ux=y$, reducing complexity from $O(n^3)$ to $O(n^2)$ once the factorisaton is known.

Cholesky Decomposition

For a Hermitian, positive-definite matrix $A$, there exists a unique lower triangular matrix $L$ such that $A=L{L}^{\ast }$. This is twice as efficient as LU and is numerically more stable.

7. Change of Basis and Similarity

If $A$ represents a linear operator $T:V\to V$ in basis $\mathcal{B}$, and $P$ is the transition matrix to a new basis ${\mathcal{B}}^{\prime }$, the representation of $T$ in the new basis is given by the similarity transformation: $B=P^{-1}AP$ Matrices $A$ and $B$ are called similar. Similarity is an equivalence relation that preserves the essential characteristics of the linear operator, known as invariants:

• $\text{tr}(A)=\text{tr}(B)$ (Trace)
• $\det (A)=\det (B)$ (Determinant)
• $p_A(\lambda )=p_B(\lambda )$ (Characteristic Polynomial and Eigenvalues)

Computational Implementation

Using scipy to solve a system and perform LU decomposition.

import numpy as np
from scipy.linalg import solve, lu

# Define a system Ax = b
A = np.array([[2, 1, 1],
              [4, 3, 3],
              [8, 7, 9]])
b = np.array([1, -1, 2])

# 1. Solve the system directly
x = solve(A, b)
print(f"Solution x: {x}")

# 2. LU Decomposition
# P: Permutation matrix, L: Lower triangular, U: Upper triangular
P, L, U = lu(A)

print("P:\n", P)
print("L:\n", L)
print("U:\n", U)

# Verification: P @ L @ U should equal A
assert np.allclose(P @ L @ U, A)

Advanced Assessment