Computing Matrix-Vector Products by Columns

The Columns as Building Blocks

A matrix-vector product can be viewed as a recipe for combining the columns of a matrix. Each entry of the vector tells us how much of the corresponding column to use. This perspective makes the product more than a list of arithmetic operations: it shows exactly how the vector’s coefficients determine a weighted sum of columns.

Let \(m,n\in\mathbb{N}\), let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and let \(\mathbf{x}\in\mathbb{R}^n\). Write the columns of \(\mathbf{A}\) as \(\mathbf{a}_1,\dots,\mathbf{a}_n\), and write the entries of \(\mathbf{x}\) as \(x_1,\dots,x_n\). Each column is a vector in \(\mathbb{R}^m\), so the weighted sum \(x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\) is also in \(\mathbb{R}^m\).

For computing by columns, the theorem gives a direct procedure: identify every column, multiply each column by the entry of \(\mathbf{x}\) in the same position, then add the resulting vectors. The \(j\)th entry of \(\mathbf{x}\) must be paired with the \(j\)th column—not with a row, and not with a column chosen because its entries look similar. There is one coefficient-column pair for each of the \(n\) columns.

The product is an \(m\)-entry vector because each column has \(m\) entries and adding the scaled columns keeps that length. The input \(\mathbf{x}\) has \(n\) entries because it supplies one coefficient for each column. These observations are useful as a quick setup check, but the calculation itself is the weighted sum.

A Small Result About the Coefficients

The column formula also makes some basic cases precise. Let \(\mathbf{e}_j\in\mathbb{R}^n\) denote the standard basis vector whose \(j\)th entry is \(1\) and whose other entries are \(0\). Using \(\mathbf{e}_j\) as the input selects one column.

Proof. By the column formula, \(\mathbf{A}\mathbf{0}=0\mathbf{a}_1+\cdots+0\mathbf{a}_n=\mathbf{0}\), since every scalar multiple \(0\mathbf{a}_i\) is the zero vector and a sum of zero vectors is zero. For \(\mathbf{e}_j\), its \(j\)th entry is \(1\) and all its other entries are \(0\). Thus the column formula gives \(\mathbf{A}\mathbf{e}_j=0\mathbf{a}_1+\cdots+0\mathbf{a}_{j-1}+1\mathbf{a}_j+0\mathbf{a}_{j+1}+\cdots+0\mathbf{a}_n=\mathbf{a}_j\). \(\square\)

Another useful observation describes what happens when just one coefficient changes. It does not require calculating the entire product again.

Proof. Apply the column formula to each product and subtract: $$ \mathbf{A}\mathbf{x}-\mathbf{A}\mathbf{y} =(x_1-y_1)\mathbf{a}_1+\cdots+(x_n-y_n)\mathbf{a}_n. $$ For every \(i\ne j\), the agreement of \(\mathbf{x}\) and \(\mathbf{y}\) in entry \(i\) gives \(x_i-y_i=0\). All those terms are zero vectors, leaving only \((x_j-y_j)\mathbf{a}_j\), as claimed. \(\square\)

Computing the Weighted Sum

This procedure gives the right result because the column formula states that the product is exactly that weighted sum. It is not necessary for \(\mathbf{A}\) to be square, and the columns do not need to be different. A zero coefficient contributes a zero vector; a negative coefficient reverses the direction of its column before scaling; and a fractional coefficient scales the column by that fraction.

Fractions and Repeated Columns

Common Mistakes and a Reliable Check

Pairing a coefficient with the wrong column. In the last example, the second coefficient is \(-1\), and it belongs to the second column \((2,1)^{\top}\). A mistaken pairing might use it on the third column and write \(4\mathbf{a}_1+2\mathbf{a}_2-\mathbf{a}_3\). This incorrect sum is \((8,4)^{\top}+(4,2)^{\top}+(0,3)^{\top}=(12,9)^{\top}\), not \((6,-3)^{\top}\). The correction is to preserve the index pairing: \(x_1\) multiplies \(\mathbf{a}_1\), \(x_2\) multiplies \(\mathbf{a}_2\), and \(x_3\) multiplies \(\mathbf{a}_3\).

Dropping a minus sign. A negative coefficient scales every entry of its column by a negative number. For instance, \(-2(3,-1)^{\top}=(-6,2)^{\top}\), not \((-6,-2)^{\top}\). It is safest to write the scaled column as its own vector before adding.

Ignoring a zero coefficient’s position. A zero coefficient removes that column’s contribution, but it does not change the pairing of later coefficients. In the second example, the coefficient \(0\) removes \(\mathbf{a}_1\); the coefficient \(3\) still multiplies \(\mathbf{a}_2\), and \(-2\) still multiplies \(\mathbf{a}_3\).

A reliable final check is to list the products \(x_j\mathbf{a}_j\) again and add corresponding entries. This catches sign errors and missed columns while keeping the calculation in the column-based form. If a column is repeated, combining its coefficients can provide an additional check, but the original coefficient-column pairs should remain visible until the scaling has been done.

Why the Column View Is Useful

The column formula exposes the role of the input vector: it specifies a particular weighted combination of the columns. If one coefficient is zero, its column has no effect on that product. If a coefficient changes, the corresponding column is the contribution that changes, as the proposition above states. If two columns are equal, their contributions can be combined by adding their coefficients. These observations are useful when interpreting a matrix-vector product as well as when calculating it.

For any matrix with \(n\) columns, this method uses exactly \(n\) coefficients and produces a vector with the same number of entries as each column. Keeping the columns in order, scaling each one by its matching entry, and checking the resulting sum gives a consistent way to compute \(\mathbf{A}\mathbf{x}\), whether the matrix is square or rectangular.