Matrices, Determinants, and Inverses
Pillar: CHAIN — "Matrix multiplication chains transformations; matrix exponentiation speeds up recurrence chains."
What Is a Matrix?
A matrix is a rectangular grid of numbers arranged in rows and columns. An \(m \times n\) matrix has \(m\) rows and \(n\) columns.
This is a \(2 \times 3\) matrix. We refer to the entry in row \(i\), column \(j\) as \(A_{ij}\). Here \(A_{12} = 2\) and \(A_{23} = 6\).
Special Matrices
| Type | Description | Example (\(2 \times 2\)) |
|---|---|---|
| Square | Same number of rows and columns | \(\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\) |
| Identity (\(I\)) | 1s on diagonal, 0s elsewhere | \(\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\) |
| Zero | All entries are 0 | \(\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}\) |
| Diagonal | Non-zero only on diagonal | \(\begin{pmatrix} 3 & 0 \\ 0 & 7 \end{pmatrix}\) |
Matrix Addition and Scalar Multiplication
Addition
Add matrices of the same size entry by entry:
Scalar Multiplication
Multiply every entry by the scalar:
Matrix Multiplication
This is the most important operation. To multiply \(A\) (\(m \times k\)) by \(B\) (\(k \times n\)), the result \(C = AB\) is an \(m \times n\) matrix where:
Each entry of \(C\) is the dot product of a row of \(A\) with a column of \(B\).
Requirement
The number of columns of \(A\) must equal the number of rows of \(B\):
Worked Example
Matrix Multiplication Is NOT Commutative
In general, \(AB \ne BA\). This is a fundamental difference from number multiplication.
Example: Let \(A = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}\) and \(B = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}\).
Completely different results.
Properties That DO Hold
- Associative: \((AB)C = A(BC)\)
- Distributive: \(A(B + C) = AB + AC\)
- Identity: \(AI = IA = A\)
The Determinant
The determinant of a square matrix is a single number that captures essential information about the matrix.
2×2 Determinant
Example:
Geometric Meaning
The absolute value of the determinant equals the area scale factor of the linear transformation. If a matrix maps the unit square to a parallelogram, \(|\det A|\) is the area of that parallelogram.
- \(\det A > 0\): the transformation preserves orientation
- \(\det A < 0\): the transformation reverses orientation (mirror)
- \(\det A = 0\): the transformation collapses a dimension (not invertible)
3×3 Determinant
Expand along the first row (cofactor expansion):
Example:
Determinant is 0, so this matrix is singular (not invertible).
Key Properties of Determinants
| Property | Formula |
|---|---|
| Multiplicative | \(\det(AB) = \det(A) \cdot \det(B)\) |
| Transpose | \(\det(A^T) = \det(A)\) |
| Inverse | \(\det(A^{-1}) = \frac{1}{\det(A)}\) |
| Scalar | \(\det(cA) = c^n \det(A)\) for \(n \times n\) matrix |
| Swap rows | Changes sign of determinant |
Matrix Inverse
The inverse of a square matrix \(A\) is the matrix \(A^{-1}\) such that:
An inverse exists if and only if \(\det A \ne 0\).
2×2 Inverse Formula
Swap the diagonal entries, negate the off-diagonal entries, divide by the determinant.
Example
Verify: \(AA^{-1} = \begin{pmatrix} 2 \cdot 3 + 1 \cdot (-5) & 2(-1)+1 \cdot 2 \\ 5 \cdot 3 + 3(-5) & 5(-1)+3 \cdot 2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\) ✓
Matrix Transformations
Matrices represent linear transformations in 2D and 3D. Multiply a transformation matrix by a point (as a column vector) to transform it.
Common 2D Transformations
| Transformation | Matrix |
|---|---|
| Rotation by \(\theta\) CCW | \(\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}\) |
| Reflection over \(x\)-axis | \(\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\) |
| Reflection over \(y\)-axis | \(\begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}\) |
| Scaling by \((s_x, s_y)\) | \(\begin{pmatrix} s_x & 0 \\ 0 & s_y \end{pmatrix}\) |
| Reflection over \(y = x\) | \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) |
Example: Rotation
Rotate the point \((1, 0)\) by \(90°\) counterclockwise:
The point \((1, 0)\) maps to \((0, 1)\). Correct — a \(90°\) CCW rotation.
Composing Transformations
To apply transformation \(A\) then transformation \(B\), multiply \(BA\) (right to left). The CHAIN pillar: matrix multiplication chains transformations together.
Matrix Exponentiation: The CP Power Tool
If a matrix \(M\) represents one "step" of a transformation or recurrence, then \(M^n\) represents \(n\) steps. We can compute \(M^n\) in \(O(\log n)\) matrix multiplications using binary exponentiation (the same technique as modular exponentiation).
Fibonacci via Matrix Exponentiation
The Fibonacci recurrence \(F_n = F_{n-1} + F_{n-2}\) can be written as:
Applying this \(n\) times:
Computing \(M^n\) with binary exponentiation takes \(O(\log n)\) matrix multiplications. For \(2 \times 2\) matrices, each multiplication is \(O(1)\), so we get \(F_n\) in \(O(\log n)\) time.
This is a major technique in competitive programming — it works for any linear recurrence, not just Fibonacci. You will explore it thoroughly in Ch10 of this course.
General Pattern
Any recurrence of the form \(a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}\) can be expressed as:
where \(M\) is a \(k \times k\) companion matrix. Raising \(M\) to the \(n\)-th power gives you the \(n\)-th term in \(O(k^3 \log n)\).
Practice Problems
Problem 1. Compute \(AB\) for \(A = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix}\), \(B = \begin{pmatrix} 1 & 0 \\ 2 & 5 \end{pmatrix}\).
Solution
\(AB = \begin{pmatrix} 2(1)+3(2) & 2(0)+3(5) \\ 1(1)+4(2) & 1(0)+4(5) \end{pmatrix} = \begin{pmatrix} 8 & 15 \\ 9 & 20 \end{pmatrix}\)
Problem 2. Find \(\det \begin{pmatrix} 5 & 3 \\ 2 & 7 \end{pmatrix}\).
Solution
\(\det = 5 \cdot 7 - 3 \cdot 2 = 35 - 6 = 29\).
Problem 3. Find the inverse of \(\begin{pmatrix} 4 & 7 \\ 2 & 6 \end{pmatrix}\).
Solution
\(\det = 24 - 14 = 10\).
\(A^{-1} = \frac{1}{10}\begin{pmatrix} 6 & -7 \\ -2 & 4 \end{pmatrix} = \begin{pmatrix} 0.6 & -0.7 \\ -0.2 & 0.4 \end{pmatrix}\)
Problem 4. What is the determinant of the identity matrix \(I_n\)?
Solution
\(\det(I_n) = 1\) for any \(n\).
Problem 5. The recurrence \(a_n = 3a_{n-1} + 2a_{n-2}\) with \(a_0 = 1, a_1 = 1\) can be written in matrix form. Write the companion matrix \(M\).
Solution
So \(\begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix} = M \begin{pmatrix} a_{n-1} \\ a_{n-2} \end{pmatrix}\).
Problem 6. If \(\det(A) = 3\) and \(\det(B) = -5\), what is \(\det(AB)\)?
Solution
\(\det(AB) = \det(A) \cdot \det(B) = 3 \cdot (-5) = -15\).