Proving Column-Space Membership Is Solvability

From Column Combinations to Equations

A matrix equation \(\mathbf{A}\mathbf{x}=\mathbf{b}\) asks whether some combination of the columns of \(\mathbf{A}\) produces \(\mathbf{b}\). The equation is not a separate question from column-space membership: its unknown entries are precisely the coefficients in that combination. Making this connection explicit lets us move between a geometric description of a set of vectors and a solvability question about a system of equations.

Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), with columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\in\mathbb{R}^m\). The column space consists of all linear combinations of those columns. The target vector \(\mathbf{b}\) must have \(m\) entries, while the coefficient vector \(\mathbf{x}\) must have \(n\) entries. These dimensions matter: \(\mathbf{A}\mathbf{x}\) is defined for \(\mathbf{x}\in\mathbb{R}^n\), and its result lies in \(\mathbb{R}^m\).

If \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\), the column formula for matrix-vector multiplication gives \(\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\). Thus, a proposed coefficient list \(c_1,\dots,c_n\) can be placed, in the same order, into \(\mathbf{x}\). Then the column combination and the matrix product are the same vector.

The Column-Space Membership Criterion

Proof. First suppose \(\mathbf{b}\in\operatorname{Col}\mathbf{A}\). By the definition of column space, there are real numbers \(c_1,\dots,c_n\) such that \(\mathbf{b}=c_1\mathbf{a}_1+\cdots+c_n\mathbf{a}_n\). Define \(\mathbf{x}=(c_1,\dots,c_n)^{\top}\). By the column formula for matrix-vector multiplication, \(\mathbf{A}\mathbf{x}=c_1\mathbf{a}_1+\cdots+c_n\mathbf{a}_n=\mathbf{b}\), so the equation has a solution. Conversely, suppose \(\mathbf{A}\mathbf{x}=\mathbf{b}\) for some \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\). The same formula gives \(\mathbf{b}=\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\), which is a linear combination of the columns. Hence \(\mathbf{b}\in\operatorname{Col}\mathbf{A}\). Both implications hold, proving the equivalence. \(\square\)

The proof relies on matching coefficients in order. The coefficient of \(\mathbf{a}_1\) becomes the first entry of \(\mathbf{x}\), the coefficient of \(\mathbf{a}_2\) becomes its second entry, and so on. The entries of \(\mathbf{b}\), in contrast, are the coordinates of the resulting vector; they are not generally the coefficients used to form it.

When No Coefficients Can Produce the Target

The theorem also turns failure of membership into a statement about equations: if no coefficient vector can produce \(\mathbf{b}\), then \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has no solution. A contradiction among the coordinate equations is enough to prove that no such coefficients exist.

One Target Can Have More Than One Coefficient List

Membership asks whether at least one coefficient list exists. It does not, by itself, say that the list is unique. When columns can combine redundantly, different coefficient vectors can give the same target. The next example displays two solutions directly, so each can be checked by multiplication.

There is a simple general fact behind the canonical solutions obtained by choosing one coefficient to be \(1\) and the others \(0\).

Proof. By the column formula, \(\mathbf{A}\mathbf{e}_j\) is the combination of the columns of \(\mathbf{A}\) whose coefficient on \(\mathbf{a}_j\) is \(1\) and whose other coefficients are \(0\). This combination equals \(\mathbf{a}_j\), so \(\mathbf{A}\mathbf{e}_j=\mathbf{a}_j\). The equation exhibits \(\mathbf{a}_j\) as a column combination, and therefore \(\mathbf{a}_j\in\operatorname{Col}\mathbf{A}\). \(\square\)

A Common Coefficient-Vector Mistake

Do not use the target’s coordinates as the column coefficients automatically. For example, take \(\mathbf{A}=\begin{bmatrix}1&1\\0&1\end{bmatrix}\) and \(\mathbf{b}=(3,2)^{\top}\). A mistaken calculation uses the entries of \(\mathbf{b}\) as the coefficient vector and claims \(\mathbf{A}(3,2)^{\top}=\mathbf{b}\). In fact,

The corrected coefficient vector is \(\mathbf{x}=(1,2)^{\top}\), since \[ \begin{bmatrix}1&1\\0&1\end{bmatrix} \begin{bmatrix}1\\2\end{bmatrix} = \begin{bmatrix}1(1)+1(2)\\0(1)+1(2)\end{bmatrix} = \begin{bmatrix}3\\2\end{bmatrix} =\mathbf{b}. \] The entries of \(\mathbf{x}\) weight the columns; the entries of \(\mathbf{b}\) describe the resulting vector. They have different roles, even when both vectors happen to have the same number of entries.

Using the Equivalence

The criterion gives two equivalent ways to describe the same question. To show that a target belongs to the column space, provide coefficients and check the resulting combination, or provide a solution and check \(\mathbf{A}\mathbf{x}=\mathbf{b}\). To show that it does not belong, show that no coefficient list can work, often by finding incompatible coordinate equations. In every case, the number of coefficients is determined by the number of columns, while the number of coordinates in the target is determined by the number of rows.

The important scope of the conclusion is existence. A verified solution proves membership, but the theorem does not claim that the solution is unique. The example with two different coefficient vectors shows why that distinction matters: both vectors produce the same \(\mathbf{b}\), so the target is in the column space even though its representation is not unique.