Why does span require having a pivot in each row? Is there is a row with all zeroes, doesn't that mean there is at least one solution, meaning that the columns in the matrix do span? Thank you.
[Math] Why does span require having a pivot in each row
linear algebra
Related Solutions
[Math] Can a set of 4 vectors with 3 entries each only span R2 if the third row reduces to all zeros
So the question is to find the span of $v_{1} = \begin{bmatrix} 1 \\ 0 \\ 2 \\ \end{bmatrix}$, $v_{2} = \begin{bmatrix} 3 \\ 1 \\ 1 \\ \end{bmatrix}$, $v_{3} = \begin{bmatrix} 9 \\ 4 \\ -2 \\ \end{bmatrix}$, and $v_{4} = \begin{bmatrix} -7 \\ 3 \\ 1 \\ \end{bmatrix}$.
Before trying to solve this problem, it is important to know what span means. The first thing you need to know is where the vectors live. To figure this out, count the number of components in one of the vectors. In this case, there are 3 components in each vector, so these vectors live in $\mathbb{R}^{3}$. The first component corresponds to the $x$-axis, the second component corresponds to the $y$-axis, and the third component corresponds to the $z$-axis.
Now, if we take two linearly independent vectors, say $v_{1} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$ and $v_{2} = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}$, then these vectors clearly live in $\mathbb{R}^{3}$, since they each have 3 components. Since they are linearly independent, and there are 2 of them, they span a plane in $\mathbb{R}^{3}$. This particular plane is isomorphic to $\mathbb{R}^{2}$, but it is not $\mathbb{R}^{2}$, because vectors in $\mathbb{R}^{2}$ all look like $\begin{bmatrix} x \\ y \\ \end{bmatrix}$ (i.e., they have 2 components only). A plane in $\mathbb{R}^{3}$ is clearly 2-dimensional since that is how we define a plane, but we do not describe it as $\mathbb{R}^{2}$. Instead, we simply say it is a plane in $\mathbb{R}^{3}$.
Here is an example of what I mean: span$\left \{\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \right \}$ is the $XY$-plane in $\mathbb{R}^{3}$, while span$\left \{\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \right \}$ is the $XZ$-plane in $\mathbb{R}^{3}$, and span$\left \{\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \right \}$ is the $YZ$-pane in $\mathbb{R}^{3}$. All three of the spans I just mentioned are isomorphic to $\mathbb{R}^{2}$, but they are distinct planes in $\mathbb{R}^{3}$, which is why we must describe them as planes in $\mathbb{R}^{3}$, rather than just as $\mathbb{R}^{2}$. When described as planes, they can be differentiated from each other, which is good because they are different planes.
Now, on to your question, as you correctly stated, to determine which vectors are linearly independent (in order to determine the dimension of the span), we put the vectors as columns in a matrix and reduce to RREF. So after doing that, we get that
$\begin{bmatrix} 1 & 3 & 9 & -7 \\ 0 & 1 & 4 & 3 \\ 2 & 1 & -2 & 1 \\ \end{bmatrix}$ reduces to $\begin{bmatrix} 1 & 0 & -3 & 0 \\ 0 & 1 & 4 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$
We see that there are three pivots! The number of pivots is the number of linearly independent columns, and the pivots correspond to the linearly independent columns, so the vectors $ \left \{ \begin{bmatrix} 1 \\ 0 \\ 2 \\ \end{bmatrix}, \begin{bmatrix} 3 \\ 1 \\ 1 \\ \end{bmatrix}, \begin{bmatrix} -7 \\ 3 \\ 1 \\ \end{bmatrix} \right \}$ (which are $v_{1}$, $v_{2}$, and $v_{4}$) are the linearly independent ones, and $v_{3}$ is linearly dependent on them. Since there are three linearly independent vectors, the span of all four vectors is equal to the span of the three linearly independent ones. Three linearly independent vectors span a subspace that is 3-dimensional. But these vectors live in $\mathbb{R}^{3}$, which is 3-dimensional itself, so their span must be equal to $\mathbb{R}^{3}$. If these vectors happened to live in $\mathbb{R}^{4}$, then their span would be a 3-dimensional subspace of $\mathbb{R}^{4}$.
So to answer your question, these four vectors could have spanned a 2-dimensional subspace of $\mathbb{R}^{3}$ if only two of the four were linearly independent. But we had three pivots in our matrix, so three linearly independent vectors, which meant the span of the four was equal to the span of the three linearly independent vectors (i.e., span$\{ v_{1}, v_{2}, v_{3}, v_{4} \} = $ span$\{ v_{1}, v_{2}, v_{4} \}$), and they spanned all of $\mathbb{R}^{3}$ in this case because they live in the 3-dimensional space and their span is 3-dimensional.
Part I: Find a BFS
OP has transformed the LP to this max problem.
\begin{array}{rrr} \max z &= -3y_1 + y_2 - 2y_3 & \\ \text{s.t.} & -2y_1 + y_2 - y_3 \le& 1 \\ & -y_1 \phantom{-y_2} - 2y_3 \le& -2 \\ & 7y_1-4y_2+6y_3 \le& -1 \\ & y_1,y_2,y_3 \ge 0 \end{array}
In the given initial tableau, the problem is actually
$$ \begin{array}{rrrr} \max z =& -3y_1 + y_2 - 2y_3 & & \\ \text{s.t.} & -2y_1 + y_2 - y_3 &+ s_1 =& 1 \\ & -y_1 \phantom{-y_2} - 2y_3 &+ s_2 =& -2 \\ & 7y_1-4y_2+6y_3 &+ s_3 =& -1 \\ & y_1,y_2,y_3,s_1,s_2,s_3 \ge 0 \end{array} \tag{1}\label{1} $$
The computer program handles positive variables, but the RHS shows that the current BFS is $s_1 = 1$, $s_2 = -2$ and $s_3 = -1$. This is the cause of error.
In fact, we should make RHS non-negative.
$$ \begin{array}{rrrr} \max z =& -3y_1 + y_2 - 2y_3 & & \\ \text{s.t.} & -2y_1 + y_2 - y_3 &+ s_1 =& 1 \\ & y_1 \phantom{+y_2} + 2y_3 &- s_2 =& 2 \\ & -7y_1+4y_2-6y_3 &- s_3 =& 1 \\ & y_1,y_2,y_3,s_1,s_2,s_3 \ge 0 \end{array} \tag{2}\label{2} $$
We need to find feasible solution first, so we add two more artificial non-negative variables $u_1$ and $u_2$ to the LP. (To apply simplex method, we can't have negative variables.) Since $u_1$ and $u_2$ aren't in the BFS of the actual problem \eqref{2}, we eliminate them by minimizing $u_1 + u_2$.
\begin{array}{rrrr} \max z= & -u_1 - u_2 & & \\ \text{s.t.} & -2y_1 + y_2 - y_3 &+ s_1 \phantom{+u_1} =& 1 \\ & y_1 \phantom{+y_2} + 2y_3 &- s_2 + u_1 =& 2 \\ & -7y_1+4y_2-6y_3 &- s_3 + u_2 =& 1 \\ & y_1,y_2,y_3,s_1,s_2,s_3,u_1,u_2 \ge 0 \end{array}
The actual intial simplex tableau
y_1 y_2 y_3 s_1 s_2 s_3 u_1 u_2 RHS
s_1 -2 1 -1 1 0 0 0 0 1
u_1 1 0 2 0 -1 0 1 0 2
u_2 -7 4 -6 0 0 -1 0 1 1
---------------------------------------
0 0 0 0 0 0 1 1 0
y_1 y_2 y_3 s_1 s_2 s_3 u_1 u_2 RHS
s_1 -2 1 -1 1 0 0 0 0 1
u_1 1 0 2 0 -1 0 1 0 2
u_2 -7 4* -6 0 0 -1 0 1 1
---------------------------------------
6 -4 4 0 1 1 0 0 -3
y_1 y_2 y_3 s_1 s_2 s_3 u_1 u_2 RHS
s_1 -1/4 0 1/2 1 0 1/4 0 -1/4 3/4
u_1 1 0 2* 0 -1 0 1 0 2
y_2 -7/4 1 -3/2 0 0 -1/4 0 1/4 1/4
--------------------------------------------
-1 0 -2 0 1 0 0 1 -2
y_1 y_2 y_3 s_1 s_2 s_3 u_1 u_2 RHS
s_1 -1/2 0 0 1 1/4 1/4 -1/4 -1/4 1/4
y_3 1/2 0 1 0 -1/2 0 1/2 0 1
y_2 -1 1 0 0 -3/4 -1/4 3/4 1/4 7/4
--------------------------------------------
0 0 0 0 0 0 1 1 0
Now we've a BFS $y_2 = \frac74$, $y_3 = 1$ and $s_1 = \frac14$.
Part II: Find an optimal BFS
Return to \eqref{2}.
y_1 y_2 y_3 s_1 s_2 s_3 RHS
s_1 -1/2 0 0 1 1/4 1/4 1/4
y_3 1/2 0 1 0 -1/2 0 1
y_2 -1 1 0 0 -3/4 -1/4 7/4
----------------------------------
3 -1 2 0 0 0 0
y_1 y_2 y_3 s_1 s_2 s_3 RHS
s_1 -1/2 0 0 1 1/4 1/4* 1/4
y_3 1/2 0 1 0 -1/2 0 1
y_2 -1 1 0 0 -3/4 -1/4 7/4
-----------------------------------
1 0 0 0 1/4 -1/4 -1/4
y_1 y_2 y_3 s_1 s_2 s_3 RHS
s_3 -2 0 0 4 1 1 1
y_3 1/2 0 1 0 -1/2 0 1
y_2 -3/2 1 0 1 -1/2 0 2
---------------------------------
1/2 0 0 1 1/2 0 0
Hence, the optimal solution to \eqref{2} (thus the original LP) is $(y_1,y_2,y_3,s_1,s_2,s_3) = (0,2,1,0,0,1)$ with optimal value 0.
Best Answer
Here's what I think you're asking:
This question can be answered as follows. First, note that the statement "the columns of $A$ span $\Bbb R^m$" is equivalent to the statement "the equation $Ax = b$ has a solution $x \in \Bbb R^n$ for every $b \in \Bbb R^m$". Remember also that the point of row-reduction is to make solving systems of equations easier. In particular: suppose that $R$ is the row-reduced form of $A$, and that applying these row operations to $b$ produces the vector $c$. Then the equations $$ Ax = b, \qquad Rx = c $$ have exactly the same solutions. So, $Ax = b$ will have a solution for every $b$ if and only if $Rx = c$ has a solution for every $c$. However, if $R$ has a final row with only zeros, then the last row of the equation $Rx = c$ will look like $$ 0x_1 + 0x_2 + \cdots + 0x_n = c_m $$ which will only have a solution if $c_m = 0$. So, $Rx = c$ can only have a solution for every $c$ if $R$ does not have a row of zeros. So, $Rx = c$ can only have a solution for every $c$ if $R$ has a pivot in every row. So, $Ax = b$ can only have a solution for every $b$ if $R$ has a pivot in every row. So, the columns of $A$ will span $\Bbb R^m$ only if $R$ (the reduced form of $A$) has a pivot in every row.