One Coefficient Matrix, Several Targets
Suppose you are given a fixed list of vectors and asked whether several different vectors belong to their span. Testing each target separately is valid, but it repeats the same reduction of the coefficient matrix. A more efficient method is to place all the targets side by side and apply one shared sequence of row operations. Each target’s membership question is then answered by its own transformed column.
Work over \(\mathbb{R}\). Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\) be a fixed coefficient matrix, with columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\). A target \(\mathbf{b}\in\mathbb{R}^m\) belongs to \(\operatorname{Col}\mathbf{A}\), the span of the columns of \(\mathbf{A}\), exactly when there is a coefficient vector \(\mathbf{x}\in\mathbb{R}^n\) satisfying \(\mathbf{A}\mathbf{x}=\mathbf{b}\). For several targets \(\mathbf{b}_1,\dots,\mathbf{b}_k\), place them as the columns of \(\mathbf{B}=\begin{bmatrix}\mathbf{b}_1&\cdots&\mathbf{b}_k\end{bmatrix}\).
The row-reduction fact used in span-membership tests is that elementary row operations on an augmented matrix preserve the solution set of its system. Here that fact is applied simultaneously: one row operation changes each right-hand side in the same way, while leaving the unknown coefficient vector \(\mathbf{x}\) in the same system.
The Shared Reduction Test
Proof. Fix any target index \(j\). The row operations turn the augmented matrix \(\begin{bmatrix}\mathbf{A}&\mathbf{b}_j\end{bmatrix}\) into \(\begin{bmatrix}\mathbf{R}&\mathbf{c}_j\end{bmatrix}\). By preservation of the solution set under row operations, \(\mathbf{A}\mathbf{x}=\mathbf{b}_j\) has a solution exactly when \(\mathbf{R}\mathbf{x}=\mathbf{c}_j\) has a solution. By the definition of column space, the first system has a solution exactly when \(\mathbf{b}_j\in\operatorname{Col}\mathbf{A}\). Any solution \(\mathbf{x}\) gives \(\mathbf{A}\mathbf{x}=\mathbf{b}_j\), so its entries are the coefficients on the original columns of \(\mathbf{A}\). The argument applies to each \(j\) using the same row operations, proving the claim for every target. \(\square\)
To decide consistency from the reduced system, inspect rows where the coefficient part is zero. A row of the form \(\begin{bmatrix}0&\cdots&0\mid d\end{bmatrix}\) represents the equation \(0=d\). It rules out membership when \(d\ne0\). If every such row has right-hand side zero, the system is consistent. The next result justifies both directions of this test, including when the system has free variables.
Proof. If a zero row of \(\mathbf{R}\) has corresponding right-hand side \(d\ne0\), its equation is \(0=d\), which has no solution. Thus consistency requires every such entry to be zero. Conversely, suppose every zero row has right-hand side zero. In each nonzero row, there is a pivot variable, and each pivot is in its own column. Assign zero to every free variable. Then the equation in each pivot row determines its pivot variable to equal the right-hand-side entry in that row. These assignments satisfy every pivot-row equation, and the zero-row equations read \(0=0\). Therefore a solution exists. \(\square\)
Worked Examples
Worked Example: Targets That Do and Do Not Belong
Let \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\), and test the targets \(\mathbf{b}_1=(2,3,5)\), \(\mathbf{b}_2=(1,1,4)\), and \(\mathbf{b}_3=(0,2,2)\) in \(\mathbb{R}^3\). Reduce the coefficient block once while applying each operation to all three targets.
Subtract \(R_1\) from \(R_3\), then subtract the new \(R_2\) from \(R_3\):
The first two columns are the coefficient block. The last three columns are the transformed targets. The last row requires the third coordinate of a target to equal the sum of its first two coordinates. For \(\mathbf{b}_1\), the transformed right-hand side is \((2,3,0)\), so the system is consistent. The reduced equations give \(x_1=2\), \(x_2=3\). Thus \(\mathbf{b}_1=2\mathbf{a}_1+3\mathbf{a}_2\).
For \(\mathbf{b}_2\), the transformed right-hand side is \((1,1,2)\). The last equation is \(0=2\), so the target is not in the column space. For \(\mathbf{b}_3\), the transformed right-hand side is \((0,2,0)\). The equations give \(x_1=0\), \(x_2=2\), so \(\mathbf{b}_3=0\mathbf{a}_1+2\mathbf{a}_2\).
Checks: \(\mathbf{A}\begin{bmatrix}2\\3\end{bmatrix}=(2,3,5)=\mathbf{b}_1\), since the third coordinate is \(2+3=5\). Also \(\mathbf{A}\begin{bmatrix}0\\2\end{bmatrix}=(0,2,2)=\mathbf{b}_3\). For the failed target, every vector \(\mathbf{A}\mathbf{x}\) has third coordinate \(x_1+x_2\), while \(\mathbf{b}_2\) has third coordinate \(4\ne1+1\). This confirms the inconsistency.
Worked Example: Recovering Coefficients When There Are Free Variables
Let \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\), with targets \(\mathbf{b}_1=(3,4)\), \(\mathbf{b}_2=(-1,2)\), and \(\mathbf{b}_3=(4,-1)\). The coefficient matrix has three columns but only two rows, so a consistent system may have free variables. Reduce once:
For each target, column 3 of the coefficient block is free. Set \(x_3=t\), where \(t\in\mathbb{R}\). The equations from the first target give \(x_1-2t=-5\) and \(x_2+t=4\). Hence \((x_1,x_2,x_3)=(-5+2t,4-t,t)\). For the second target, the equations give \(x_1-2t=-5\) and \(x_2+t=2\), so \((x_1,x_2,x_3)=(-5+2t,2-t,t)\). For the third, they give \(x_1-2t=6\) and \(x_2+t=-1\), so \((x_1,x_2,x_3)=(6+2t,-1-t,t)\).
Checks: For the first solution family, the original matrix product has coordinates \((-5+2t)+2(4-t)=3\) and \((4-t)+t=4\). For the second, the coordinates are \((-5+2t)+2(2-t)=-1\) and \((2-t)+t=2\). For the third, they are \((6+2t)+2(-1-t)=4\) and \((-1-t)+t=-1\). Thus all three targets belong to \(\operatorname{Col}\mathbf{A}\), with a family of coefficient choices for each.
Worked Example: A Batch With Unique Coefficients
Let \(\mathbf{A}=\begin{bmatrix}1&1\\1&-1\end{bmatrix}\), and test \(\mathbf{b}_1=(4,2)\), \(\mathbf{b}_2=(0,6)\), and \(\mathbf{b}_3=(1,0)\). Subtract \(R_1\) from \(R_2\), multiply \(R_2\) by \(-\tfrac12\), then subtract \(R_2\) from \(R_1\):
There are no zero rows in the coefficient block, so each target is consistent, and the pivot equations give unique coefficients. They are \((3,1)\) for \(\mathbf{b}_1\), \((3,-3)\) for \(\mathbf{b}_2\), and \((\tfrac12,\tfrac12)\) for \(\mathbf{b}_3\).
Checks: \(\mathbf{A}\begin{bmatrix}3\\1\end{bmatrix}=(4,2)\), \(\mathbf{A}\begin{bmatrix}3\\-3\end{bmatrix}=(0,6)\), and \(\mathbf{A}\begin{bmatrix}\tfrac12\\\tfrac12\end{bmatrix}=(1,0)\). Each product matches its original target.
Reading the Reduction Carefully
The target columns do not change the coefficient variables: every target is tested against the same original columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\). What changes during the reduction is the right-hand side for each system. This is why the target columns must undergo every row operation used on the coefficient block.
When \(\mathbf{R}\) is in reduced row echelon form, a target passes the membership test precisely when its transformed entries in all zero rows are zero. For a passing target, the pivot equations give the coefficients. If there are free variables, choosing particular values for them gives one expression; allowing them to vary describes all expressions. A failed target has no coefficient choice that can make the original column combination equal that target.
Common Pitfall: Reducing Only the Coefficient Block
Suppose the matrix in the third example is reduced to \(\mathbf{I}_2\), but the target \((4,2)\) is mistakenly left unchanged. Reading the unreduced target as the coefficient vector gives the incorrect answer \((4,2)\). Substitution exposes the error: \(\mathbf{A}\begin{bmatrix}4\\2\end{bmatrix}=(6,2)\), not \((4,2)\).
The correct row operations must also be applied to the target. In the worked example they transform \((4,2)\) into \((3,1)\), and \(\mathbf{A}\begin{bmatrix}3\\1\end{bmatrix}=(4,2)\). A coefficient matrix can be reduced once for many tests, but only if every target is carried through that same reduction.
Batching targets is useful whenever the same set of generators is tested against several vectors. It avoids repeated arithmetic and makes the shared structure visible: the coefficient block is reduced once, each transformed target is checked against the resulting zero rows, and each successful column supplies its own coefficient equations.
Check Your Understanding
For each question, distinguish the transformed right-hand side from the original target.
- In a shared reduction, what must be done to each target column whenever a row operation is applied?
- If a reduced coefficient row is all zeros and the corresponding transformed target entry is \(5\), what does that imply about membership?
- For \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\), find one coefficient vector expressing \((3,4)\) by setting the free variable to zero.
- Why can one shared reduction produce different coefficient vectors for different targets?
- For \(\mathbf{A}=\begin{bmatrix}1&1\\1&-1\end{bmatrix}\), verify by multiplication whether \((3,-3)\) represents the target \((0,6)\).
