How to formally show a vector is not in a space? 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}$
 A: 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.
A: 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.)
A: 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.
A: 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$.
