Unit 1: Matrix Algebra

1. Introduction to Matrices and Systems of Linear Equations

Matrices are fundamental mathematical arrays used across computational engineering, graphics, signal processing, and numerical physics. An $m \times n$ matrix contains $m$ rows and $n$ columns of scalar entries.

Elementary Row Operations

Elementary row operations (EROs) transform a matrix into simpler canonical forms without altering the solution space of the corresponding linear system:

1. Row Swapping ($R_i \leftrightarrow R_j$): Interchanging two distinct rows.
2. Scalar Multiplication ($R_i \leftarrow k R_i, k \neq 0$): Scaling every entry of a row by a non-zero scalar.
3. Row Addition / Elimination ($R_i \leftarrow R_i + k R_j$): Adding a scalar multiple of row $j$ to row $i$.

Each elementary row operation corresponds to pre-multiplying the matrix by an elementary matrix $E$, formed by applying the identical operation to the identity matrix $I$. Because every elementary matrix is non-singular, EROs preserve row equivalence and matrix rank.

2. Row Echelon Form (REF) and Reduced Row Echelon Form (RREF)

A matrix is in Row Echelon Form (REF) if:

• All non-zero rows lie strictly above any rows consisting entirely of zeros.
• The leading coefficient (pivot) of a non-zero row is positioned strictly to the right of the pivot in the preceding row.
• All entries directly below a pivot are zero.

A matrix is in Reduced Row Echelon Form (RREF) if, in addition to the REF criteria:

• Every pivot entry equals $1$.
• Each pivot is the sole non-zero entry in its entire column (entries both above and below the pivot are zero).

While a matrix can have multiple row echelon forms depending on the sequence of operations, its reduced row echelon form is strictly unique.

3. Rank of a Matrix and the Rank-Nullity Theorem

The rank of a matrix $A$, denoted $\text{rank}(A)$ or $\rho(A)$, is defined as:

• The maximum number of linearly independent row vectors (row rank).
• The maximum number of linearly independent column vectors (column rank).
• The order of the largest non-zero sub-determinant (minor) of $A$.
• The total count of pivot positions (non-zero rows) in its row echelon form.

Fundamental Rank Properties:

• For an $m \times n$ matrix $A$: $0 \le \text{rank}(A) \le \min(m, n)$.
• $\text{rank}(A) = \text{rank}(A^T) = \text{rank}(A^T A)$.
• Rank-Nullity Theorem: For an $m \times n$ matrix representing a linear transformation $T: \mathbb{R}^n \to \mathbb{R}^m$:
  $\text{rank}(A) + \text{nullity}(A) = n$
  where $\text{nullity}(A)$ represents the dimension of the null space $\ker(A) = \{x \in \mathbb{R}^n : Ax = 0\}$.

4. Matrix Inversion and Gauss-Jordan Elimination

A square matrix $A \in \mathbb{R}^{n \times n}$ is invertible (non-singular) if there exists a matrix $A^{-1}$ such that:
$A A^{-1} = A^{-1} A = I_n$

Adjoint Method:

$A^{-1} = \frac{1}{\det(A)} \text{adj}(A)$
where $\text{adj}(A) = C^T$, the transpose of the cofactor matrix $C$.

Gauss-Jordan Elimination:

Construct the augmented block matrix $[A \mid I_n]$ and apply elementary row operations until the left block reduces to $I_n$:
$[A \mid I_n] \xrightarrow{\text{EROs}} [I_n \mid A^{-1}]$
If the left block cannot be reduced to $I_n$ (i.e., a zero row appears), $\det(A) = 0$ and $A$ is singular.

5. Consistency and Solutions of Linear Systems ($Ax = b$)

Let $A$ be an $m \times n$ coefficient matrix, $x$ an $n \times 1$ vector of unknowns, and $b$ an $m \times 1$ vector of constants. The augmented matrix is denoted $[A \mid b]$.

Rouché-Capelli (Consistency) Theorem:

1. Inconsistent System (No Solution):
   $\text{rank}(A) < \text{rank}([A \mid b])$
   This occurs when row reduction yields a contradictory row $[0 \; 0 \; \dots \; 0 \mid c]$ where $c \neq 0$.
2. Consistent with Unique Solution:
   $\text{rank}(A) = \text{rank}([A \mid b]) = n \quad (\text{number of variables})$
   Every column contains a pivot; no free variables exist.
3. Consistent with Infinitely Many Solutions:
   $\text{rank}(A) = \text{rank}([A \mid b]) = r < n$
   The solution space has $n - r$ free variables (degrees of freedom).

Homogeneous Linear Systems ($Ax = 0$):

• Always consistent because the trivial solution $x = 0$ always satisfies $A(0) = 0$.
• Possesses non-trivial (non-zero) solutions if and only if $\text{rank}(A) < n$. For a square matrix $n \times n$, this is equivalent to $\det(A) = 0$.

6. Eigenvalues and Eigenvectors

Let $A$ be an $n \times n$ square matrix. A scalar $\lambda \in \mathbb{C}$ is an eigenvalue of $A$ if there exists a non-zero vector $v \neq 0$ such that:
$A v = \lambda v \iff (A - \lambda I) v = 0$

Characteristic Equation:

Non-trivial solutions $v$ exist if and only if:
$\det(A - \lambda I) = 0$
This determinant expands into the characteristic polynomial $P(\lambda) = (-1)^n \lambda^n + c_{n-1} \lambda^{n-1} + \dots + \det(A)$.

Crucial Eigenvalue Theorems:

• Trace Property: The sum of all eigenvalues (counted with multiplicity) equals the trace of $A$:
  $\sum_{i=1}^n \lambda_i = \text{Tr}(A) = \sum_{i=1}^n a_{ii}$
• Determinant Property: The product of all eigenvalues equals the determinant:
  $\prod_{i=1}^n \lambda_i = \det(A)$
• Triangular Matrices: The eigenvalues of upper triangular, lower triangular, and diagonal matrices are precisely the primary diagonal elements.
• Spectral Mapping: If $\lambda$ is an eigenvalue of $A$ with eigenvector $v$:
  • $A^k$ has eigenvalue $\lambda^k$.
  • $A^{-1}$ (if invertible) has eigenvalue $\lambda^{-1} = 1/\lambda$.
  • $A + cI$ has eigenvalue $\lambda + c$.
• Algebraic vs. Geometric Multiplicity:
  • Algebraic Multiplicity ($AM$): The multiplicity of $\lambda$ as a root of $\det(A - \lambda I) = 0$.
  • Geometric Multiplicity ($GM$): The dimension of the eigenspace $E_\lambda = \text{nullity}(A - \lambda I)$.
  • Always $1 \le GM(\lambda) \le AM(\lambda)$. A matrix is diagonalizable if and only if $GM(\lambda) = AM(\lambda)$ for every eigenvalue.

7. The Cayley-Hamilton Theorem

Theorem Statement:

Every square matrix satisfies its own characteristic equation. That is, if:
$P(\lambda) = \det(A - \lambda I) = (-1)^n \lambda^n + c_{n-1} \lambda^{n-1} + \dots + c_1 \lambda + c_0 = 0$
then substituting the matrix $A$ yields the zero matrix:
$P(A) = (-1)^n A^n + c_{n-1} A^{n-1} + \dots + c_1 A + c_0 I = O$

Primary Applications:

1. Evaluating Inverse Matrices:
   If $\det(A) = c_0 \neq 0$, multiplying $P(A) = 0$ by $A^{-1}$ allows direct computation of $A^{-1}$:
   $A^{-1} = -\frac{1}{c_0} \left[ (-1)^n A^{n-1} + c_{n-1} A^{n-2} + \dots + c_1 I \right]$
2. Computing Higher Matrix Powers:
   Express $A^m$ (where $m \ge n$) as a polynomial in $A$ of degree at most $n-1$, vastly accelerating numerical computations and matrix exponentiation.