How to formally show a vector is not in a space?

Question

I'm trying to formally prove that a row vector is not in the row space of some given matrix. It is clear by visual inspection that the row cannot be written as a linear combination as the rows of the matrix. But how do I formally prove it? I cannot, of course, go through all possible linear combinations, and I believe a visual argument alone is not satisfactory.

Is there any theorem that would be contradicted by assuming some vector belongs to a row/column space when it doesn't?

I am asking this question for the general case, however the matrix and vector I'm working with, for the purposes of exposition are:

$\underline{\lambda}'= \left( \begin{array}{cc} 0 & 1 & 0 & \dots & 0\\ \end{array} \right)_{1\times(k+1)} \quad \quad X = \left( \begin{array}{cc} \underline{1}_{n1} & \underline{1}_{n1} & \underline{0}_{n1} & \dots & \underline{0}_{n1}\\ \underline{1}_{n2} & \underline{0}_{n2} & \underline{1}_{n2} & \dots & \underline{0}_{n2}\\ \vdots & \vdots & \vdots & \dots & \vdots\\ \underline{1}_{nk} & \underline{0}_{nk} & \underline{0}_{nk} & \dots & \underline{1}_{nk}\\ \\ \end{array} \right)_{N\times(k+1)}$

In my notation, an underline means a vector and $N=\sum_{i}n_{i}$

Answer 1

Generally speaking, if you want to check whether a vector $b$ is in the column space of a matrix $A$, you are looking for a solution $x$ to the system $Ax=b$. This can be done with a computer (or, if you need to do this by hand, using Gaussian elimination).

(Since your original question is about the rowspace of a matrix, just transpose the matrix before reading my above paragraph.)

Answer 2

Suppose it were in the row space. Explicitly write $\lambda'$ as some arbitrary linear combination of the rows, $\lambda' = \sum_j a_j r_j$ where the $r_j$ are the rows. Work with the coordinates to get a contradiction (e.g. the last coordinate is 0, so $a_{k+1} = 0$) and so on.

Answer 3

For this case, notice that each row has a $1$ in a column shared by no other row.

We need a $1$ in column $2$ but if we take any multiple of row 1 we are left with a non-zero value in column one. The only way to remove that $1$ is to add or subtract other rows. But, no matter which row you use, you will be left with a column than cannot be cleared.

Answer 4

Let $\underline{v}'=\begin{bmatrix}1 & -1 & -1 & \cdots & -1\end{bmatrix}$. Then observe that $X\underline{v}=0$ but that $\underline{\lambda}'\underline{v}\ne0$. In this case the nullspace of $X$ is one-dimensional and consists of all scalar multiples of $\underline{v}$.

More generally, put $X$ in reduced row-echelon form. Then read off a basis for the nullspace of $X$. (See note.) Now if $\underline{\lambda}'\underline{v}\ne0$ for some basis vector $\underline{v}$ of the nullspace, then $\underline{\lambda}'$ is not in the rowspace of $X$.

This method has the advantage that any new vector can be quickly and systematically tested for membership in the rowspace. Given a vector $\rho'$, compute $\sigma'=\rho'V$, where $V$ is the matrix whose columns are the basis vectors of the nullspace, and check whether $\sigma'=0$. Clearly you needn't always compute every element of $\sigma'$: as soon as one of the elements is found to be non-zero, the calculation can be aborted.

Note: The nullspace will have one basis vector for each free variable: a basis vector is formed by setting the element corresponding to one of the free variables to $1$, elements corresponding to all other free variables to $0$, and reading off (with an extra minus sign) elements corresponding to pivot variables that are needed to make the resulting vector null. For example, suppose the reduced row-echelon form of $X$ is $$ \begin{bmatrix} 1 & \mathbf{\color{red}{2}} & 0 & 0 & \mathbf{\color{blue}{3}}\\ 0 & \mathbf{\color{red}{0}} & 1 & 0 & \mathbf{\color{blue}{-\frac{1}{2}}}\\ 0 & \mathbf{\color{red}{0}} & 0 & 1 & \mathbf{\color{blue}{\frac{2}{3}}}\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}. $$ Columns $2$ and $5$ correspond to free variables. The corresponding null-space vectors are $$ \begin{aligned} v'_1&=\begin{bmatrix}\mathbf{\color{red}{-2}} & 1 & \mathbf{\color{red}{0}} & \mathbf{\color{red}{0}} & 0\end{bmatrix}\\ v'_2&=\begin{bmatrix}\mathbf{\color{blue}{-3}} & 0 & \mathbf{\color{blue}{\frac{1}{2}}} & \mathbf{\color{blue}{-\frac{2}{3}}} & 1\end{bmatrix} \end{aligned} $$ In your example we take column $1$ to be the one with the free variable, set the corresponding element of $v$ to $1$, and read off that all other elements need to be $-1$.