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

The Data Prophecy Chamber sends a batch of observations as vectors to the tower top, where you must apply the same linear rules to transform them en masse and reverse-solve for the unknowns.

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 these vectors en masse, and how to infer unknown parameters from observational data.

Learning Objectives

• Use matrix shape to verify if operations are valid;
• Understand matrix multiplication through the lens of 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. A matrix is a set of columns, also a kind of transformation

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

$$ A= \begin{bmatrix} a_{11}&\cdots&a_{1n}\ \vdots&\ddots&\vdots\ a_{m1}&\cdots&a_{mn} \end{bmatrix}. $$

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}$?

Why matrix multiplication can't be arbitrarily reordered

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

$$ (AB){ij}=\sum^{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.

3. Linear Transformations and Coordinate Systems

A transformation $T$ if it satisfies

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

It's a linear transformation. Once a basis is chosen, a finite-dimensional linear transformation can be represented by a matrix.

The 2D rotation matrix is:

$$ R(\theta)= \begin{bmatrix} \cos\theta&-\sin\theta\ \sin\theta&\cos\theta \end{bmatrix}. $$

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.

Translation: Translation: A 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 deficient rank 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.

5. Linear equations Go Beyond "unique 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$.

The elimination process of an augmented matrix can detect these cases. In numerical computations, validated linear algebra libraries are typically invoked rather than implementing elimination from scratch.

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)
print(np.allclose(A @ x, b))

Don't solve $A\mathbf{x}=\mathbf{b}$ by explicitly computing $A^{-1}$ and then multiplying by $\mathbf{b}$. solve It's 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.

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\times1)=(N\times1). $$

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.

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.
• Irreversible means no solution: Non-square or singular systems can still have one or infinitely many solutions.
• Inverting is a standard step in solving equations: Numerical software should prioritize direct solving or using appropriate factorizations.

Practice

1. The shape of the result of $(3\times4)(4\times2)$ is $3\times2$, and reverse multiplication does not necessarily hold because matrix multiplication is not commutative.
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\times2$ 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."