Proving Linearity of Matrix-Vector Multiplication

What Must Be Proved

A matrix-vector product is built from sums and scalar multiples of entries. This makes it plausible that multiplying by a fixed matrix should respect addition and scalar multiplication, but plausibility is not a proof. We will establish both identities by examining each coordinate of the resulting vectors. The argument works for rectangular matrices as well as square ones, provided the dimensions match.

Throughout this tutorial, scalars are real. Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and let \(\mathbf{x},\mathbf{y}\in\mathbb{R}^n\) be column vectors. The products \(\mathbf{A}\mathbf{x}\) and \(\mathbf{A}\mathbf{y}\) are in \(\mathbb{R}^m\), as is \(\mathbf{A}(\mathbf{x}+\mathbf{y})\). For \(c\in\mathbb{R}\), both \(\mathbf{A}(c\mathbf{x})\) and \(c(\mathbf{A}\mathbf{x})\) are also in \(\mathbb{R}^m\). These dimension checks tell us that the equations we want to prove are meaningful.

The word “fixed” matters: we use the same matrix \(\mathbf{A}\) throughout each identity. We do not claim that multiplying by one matrix is the same operation as multiplying by a different matrix. To prove the identities, write \(\mathbf{A}=(a_{ij})\), where \(a_{ij}\) is the entry in row \(i\) and column \(j\). If the coordinates of \(\mathbf{x}\) are \(x_1,\dots,x_n\), then the \(i\)th coordinate of \(\mathbf{A}\mathbf{x}\) is \(\sum_{j=1}^n a_{ij}x_j\). This coordinate formula is the only fact about matrix-vector multiplication needed for the proof.

The Coordinatewise Proof

Proof. Write \(x_j\) and \(y_j\) for the \(j\)th coordinates of \(\mathbf{x}\) and \(\mathbf{y}\). To prove the addition identity, fix any row index \(i\) with \(1\le i\le m\). The \(i\)th coordinate of the left-hand side is

The second equality uses distributivity of real multiplication over addition, applied to each term of the finite sum. The last expression is the \(i\)th coordinate of \(\mathbf{A}\mathbf{x}+\mathbf{A}\mathbf{y}\). Since this equality holds for every \(i\) from \(1\) to \(m\), the two vectors have equal coordinates and therefore are equal.

For scalar multiplication, fix the same kind of index \(i\). Then

Here \(c\) can be any real number, including \(0\); the calculation does not divide by \(c\) or require it to be nonzero. Again, equality in every coordinate proves \(\mathbf{A}(c\mathbf{x})=c(\mathbf{A}\mathbf{x})\). Thus the function \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\) satisfies both conditions in the definition of a linear function. \(\square\)

The coordinate proof also indicates what the result does and does not say. It applies to any real \(m\times n\) matrix and inputs in \(\mathbb{R}^n\). No square-matrix assumption is needed. It also relies on using the same entries \(a_{ij}\) on both sides: the proof expands the left and right sides using one fixed matrix.

Applying Both Identities

This example uses a square matrix, but that shape is not essential. For a rectangular matrix, the input and output live in different-sized coordinate spaces. The identities still hold because they compare vectors in the same output space, \(\mathbb{R}^m\).

Combining the Identities

The two defining identities can be applied in succession. This is useful when an input is already written as a sum of scalar multiples. The statement below follows directly from the identities just proved; it does not require a new matrix rule.

Proof. Set \(\mathbf{u}=a\mathbf{x}\) and \(\mathbf{v}=b\mathbf{y}\). The addition identity gives \(\mathbf{A}(a\mathbf{x}+b\mathbf{y})=\mathbf{A}(a\mathbf{x})+\mathbf{A}(b\mathbf{y})\). Applying the scalar identity to each term gives \(\mathbf{A}(a\mathbf{x})=a(\mathbf{A}\mathbf{x})\) and \(\mathbf{A}(b\mathbf{y})=b(\mathbf{A}\mathbf{y})\). Substitution yields the stated equation. This reasoning also covers \(a=0\) or \(b=0\), because the scalar identity holds for zero scalars. \(\square\)

Consequences and a Common Mistake

The identities quickly give familiar special cases. Taking \(c=0\) in \(\mathbf{A}(c\mathbf{x})=c(\mathbf{A}\mathbf{x})\) shows that \(\mathbf{A}\mathbf{0}=\mathbf{0}\). Taking \(c=-1\) shows that \(\mathbf{A}(-\mathbf{x})=-(\mathbf{A}\mathbf{x})\). These are consequences of the scalar identity, not separate assumptions about matrix multiplication. They can also serve as quick checks on a proposed calculation.

Common mistake: applying the matrix to only one term. Consider \(\mathbf{A}=\begin{bmatrix}1&2\\0&-1\end{bmatrix}\), \(\mathbf{x}=\begin{bmatrix}1\\0\end{bmatrix}\), and \(\mathbf{y}=\begin{bmatrix}0\\1\end{bmatrix}\). A tempting but wrong calculation is \(\mathbf{A}(\mathbf{x}+\mathbf{y})=\mathbf{A}\mathbf{x}+\mathbf{y}\). It gives \(\mathbf{A}\mathbf{x}=\begin{bmatrix}1\\0\end{bmatrix}\), so the incorrect right-hand side is \(\begin{bmatrix}1\\1\end{bmatrix}\). The correction is to apply \(\mathbf{A}\) to both terms: \(\mathbf{A}\mathbf{y}=\begin{bmatrix}2\\-1\end{bmatrix}\), and therefore \(\mathbf{A}\mathbf{x}+\mathbf{A}\mathbf{y}=\begin{bmatrix}3\\-1\end{bmatrix}\). Directly, \(\mathbf{x}+\mathbf{y}=\begin{bmatrix}1\\1\end{bmatrix}\), so \(\mathbf{A}(\mathbf{x}+\mathbf{y})=\begin{bmatrix}3\\-1\end{bmatrix}\), as the addition identity requires.

When checking a linearity calculation, keep the two sides separate until each is evaluated. First compute the input sum or scaled input; then multiply by the matrix. On the other side, multiply the inputs separately and combine the resulting output vectors. Check that input vectors have \(n\) coordinates, output vectors have \(m\) coordinates, and that the final coordinates agree. This routine catches both arithmetic errors and dimension mismatches.