10.2 Matrices, Linear Transformations, and Systems of Equations: From Structure to Solvability

Last time we represented users, movies, and system state as vectors. This lesson tackles another problem: how to apply the same set of rules to transform many vectors, and how to infer unknown parameters from observational data.

Learning Objectives

• Use matrix shape to verify if operations are valid;
• Understand matrix multiplication through linear transformations and function composition;
• Use rank to determine whether a linear system contains redundant or missing information;
• Know when it's feasible to compute an inverse and when it's better to directly solve the equation.

1. Columns and Linear Transformations

An $m\times n$ matrix has $m$ rows and $n$ columns:

$$A=\left[\begin{array}{ccc}{a}_{11}& \cdots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{m1}& \cdots & a_{mn}\end{array}\right].$$

It can be understood from two perspectives:

• $n$ column vectors located in ${\mathbb{R}}^m$;
• A linear transformation that maps inputs from ${\mathbb{R}}^n$ to ${\mathbb{R}}^m$.

For an input vector $\mathbf{x}$, the product $A\mathbf{x}$ is a linear combination of the columns of the matrix, with the combination coefficients being $x_i$. So the equation $A\mathbf{x}=\mathbf{b}$ is asking: can we combine the columns of $A$ to produce $\mathbf{b}$?

2. Why Matrix Multiplication Cannot Be Reordered

If $A$ is $m\times n$ and $B$ is $n\times p$, then $AB$ is $m\times p$:

$$(AB{)}_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}.$$

The intermediate dimensions must match because the output of $B$ becomes the input of $A$. Under the column vector convention, perform $B$ first, then $A$, and the composite transformation is written as:

$$\mathbf{x}\mapsto B\mathbf{x}\mapsto A(B\mathbf{x})=(AB)\mathbf{x}.$$

In general, $AB\ne BA$, and even one of the products might not be defined. In graphics, "rotate first, then translate" versus "translate first, then rotate" yields different results, this difference stems from the order in which transformations are composed.

Rotation and nonuniform scaling demonstrate noncommutativity within the original two-dimensional space. The examples use Python 3 and NumPy 2.x:

import numpy as np

R = np.array([[0, -1], [1, 0]])
S = np.diag([2, 1])
v = np.array([1, 1])
print(R @ S @ v)  # [-1  2]
print(S @ R @ v)  # [-2  1]

3. Linear Transformations and Coordinate Systems

A transformation $T$ is linear if it satisfies

$$T(\mathbf{x}+\mathbf{y})=T(\mathbf{x})+T(\mathbf{y}),T(c\mathbf{x})=cT(\mathbf{x}),$$

Once input and output bases are chosen, a finite-dimensional linear transformation can be represented by a matrix.

The 2D rotation matrix is:

$$R(\theta )=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right].$$

import numpy as np

theta = np.pi / 2
rotation = np.array([
    [np.cos(theta), -np.sin(theta)],
    [np.sin(theta),  np.cos(theta)],
])

point = np.array([1.0, 0.0])
print(np.round(rotation @ point, 12))  # [0. 1.]

Floating-point trigonometric results are typically just near zero, so the example uses rounding for display; don't misinterpret tiny errors in the output as errors in the rotation formula.

A nonzero translation does not satisfy $T(\mathbf{0})=\mathbf{0}$, so it is not an ordinary 2D linear transformation. Graphics often introduces homogeneous coordinates, representing 2D affine transformations as 3D matrix multiplications, this is a unified extended representation, not because translation has suddenly become a linear transformation in the original space.

4. Rank describes the number of effective directions

The rank of a matrix is the maximum number of linearly independent columns, equal also to the maximum number of linearly independent rows. It tells you how many independent directions the transformation preserves.

• Full column rank means the column vectors are linearly independent;
• Rank less than number of columns indicates redundant parameters;
• A rank-deficient square matrix is non-invertible;
• A low rank of the data matrix may indicate highly correlated features or that the data lies in a low-dimensional subspace.

The determinant is defined only for square matrices. $|det(A)|$ describes the scaling factor of volume, and the sign indicates whether orientation has been reversed. $det(A)=0$ means the matrix is singular, but the determinant is not the preferred tool for assessing the numerical condition of large linear systems; in practice, factorizations, rank, and condition numbers are more relevant.

Distinguish exact rank from numerical rank. Nearly identical columns can remain exactly independent; floating-point libraries use singular-value thresholds to decide which directions are numerically distinguishable. Measurement error also matters when choosing a threshold. Strong correlation alone does not prove exact rank deficiency. See NumPy’s numerical-rank notes.

5. Linear Systems Can Have Different Numbers of Solutions

For $A\mathbf{x}=\mathbf{b}$, the following may occur:

1. Unique Solution: A full-rank square matrix is a common scenario;
2. Infinitely many solutions: free variables exist;
3. No solution: $\mathbf{b}$ is not in the column space of $A$.

Let $A$ have $n$ columns. If $\mathrm{rank}(A)<\mathrm{rank}([A\mid \mathbf{b}])$, no solution exists. Equal ranks give a unique solution when the rank is $n$, and infinitely many when it is smaller. Free variables give multiple solutions only after consistency is established. The small integer-valued examples below are well separated for numerical rank estimation:

import numpy as np

A = np.array([[1., 2.], [2., 4.]])
for b in [np.array([3., 6.]), np.array([3., 7.])]:
    print(np.linalg.matrix_rank(A),
          np.linalg.matrix_rank(np.column_stack([A, b])))
# 1 1: infinitely many solutions, x + 2y = 3
# 1 2: no exact solution

import numpy as np

A = np.array([[3.0, 1.0], [1.0, 2.0]])
b = np.array([9.0, 8.0])
x = np.linalg.solve(A, b)

print(x)                         # [2. 3.]
print(np.allclose(A @ x, b))       # True

Don't solve $A\mathbf{x}=\mathbf{b}$ by explicitly computing $A^{-1}$ and then multiplying by $\mathbf{b}$. solve is usually more efficient and avoids additional amplification of rounding errors. When a matrix is near singular, even if theoretically invertible, the results can be extremely sensitive to input errors; Chapter 12 uses the condition number to explain this phenomenon.

NumPy solve requires a full-rank square matrix; singular or nonsquare input raises LinAlgError. An allclose residual check uses a chosen tolerance and does not prove stability under input perturbations.

6. Shape Checking Is a Design Tool

Suppose a dataset $X$ has $N$ samples, each with $d$ features. If stored with "samples as rows," then the shape of $X$ is $N\times d$. The weight vector $\mathbf{w}$ is $d\times 1$, and only then does the prediction $X\mathbf{w}$ yield an $N\times 1$ output.

Labeling shapes when writing formulas allows you to detect numerous errors before running the code:

$$(N\times d)(d\times 1)=(N\times 1).$$

But having the right shape doesn't mean having the right semantics. Mistaking "user × feature" for "item × feature" might still allow matrix multiplication, but the result could be completely meaningless from a business perspective.

A NumPy array of shape (d,) differs from a column array of shape (d,1): predictions have shapes (N,) and (N,1) respectively. Subtracting (N,) predictions from (N,1) labels can broadcast to (N,N), silently changing the loss. Make both shapes match the intended calculation.

Common Misconceptions

• A matrix is a 2D array: An array is a storage form, but a matrix also carries transformation and spatial semantics.
• Multiplication order is just a syntactic difference: the order corresponds to function composition order and can change the result.
• Non-invertible means no solution: A nonsquare system can have a unique solution; a consistent singular square system has infinitely many.
• Inverting is a standard step in solving equations: Numerical software should prioritize direct solving or using appropriate factorizations.

Practice

1. State the result shape of $(3\times 4)(4\times 2)$ and explain why the reverse multiplication is undefined.
2. Compute the results of scaling followed by rotation, and rotation followed by scaling, and find a vector that differs between the two.
3. Construct a rank-1 $2\times 2$ matrix and explain where it maps the plane.
4. Write the augmented matrix for a two-variable system with no solution and one with infinitely many solutions.

Summary

A matrix maps the input space to the output space; matrix multiplication describes the composition of transformations, and rank indicates the number of independent pieces of information. The essence of a linear equation isn't "applying the inverse matrix," but rather determining whether the target lies within the column space and finding a stable solution using appropriate methods.

Next lesson: dealing with more realistic data, observations are noisy, and equations often have no exact solutions. Least squares, eigenvectors, and SVD transform "can't be exactly satisfied" into "find the most explanatory approximation."