# Linear system and subspaces

Let $S$ be a subspace of $R^n$ with dimension k and $m = n-k.$ Show that

$$\exists A \in R^{m\times n}, b\in R^m$$

Such that

$$S = \{ x \in R^n : Ax = b\}$$

My attempt consist of getting m "free variables", ie, choose m rows of a vector in S and to create a linear system following it. But I am having difficults to organize it.

Thanks!

Since $S$ has dimension $k$, you can pick a basis $b_1, \ldots, b_k$ of $S$. Extend this list by the standard basis vectors $e_1, \ldots, e_n$, and apply the Gram-Schmidt process, tossing out any vector that becomes zero along the way. You'll end up with a list $$b'_1, b'_2, \ldots, b'_k, c_1, \ldots, c_m$$ of orthonormal vectors, the first $k$ of which span $S$, and the remaining $m$ of which span the orthogonal complement of $S$. Place these into an $m \times n$ matrix, $A$ with the $i$th column being the vector $c_i$. $S$ is then exactly the nullspace of $A$, i.e., you can pick the vector $b$ to be the zero vector.

• This is kinda confusing for me. I was thinking in something like this:math.stackexchange.com/questions/24323/… – Giiovanna Sep 15 '14 at 17:03
• That's another way to go. If you said you wanted an answer that doesn't involve orthogonality, I'd have given one. But the answer I gave is the simplest one I know, so I gave it. (It's also (almost) algorithmic, in case you needed to write code to implement something!) – John Hughes Sep 15 '14 at 17:05
• First of all, I really appreciate your help! Now, I think I need to make a correction: The A matri given is n x m, so we should take $A^T$. Now, by the Fundamental Theorem of Linear Algebra, the orthogonal of Im(A) is the nullspace of $A^T$, as desired. – Giiovanna Sep 16 '14 at 20:17
• That sounds right (although I haven't checked in detail). I almost always manage to swap rows/columns at least once per linear-algebra question. :( – John Hughes Sep 17 '14 at 2:49

Alternative answer: Pick a basis $b_1, \ldots, b_k$ of $S$. Create a matrix $M$ with these vectors (transposed) as its rows. Perform gaussian elimination on the rows to get a row-reduced matrix. Certain entries will have their leading entry (reading left to right) being "1", and all entries above and below those "leading 1"s will be zero. Call the columns containing the leading ones "good" columns, and the others "bad". Suppose that the first of those is in column 2, as in this matrix $$\begin{bmatrix} 0 & 1 & 2 & 0 & 3 \\ 0 & 0 & 0 & 1 & 4 \end{bmatrix}$$ Columns 2 and 4 are good; 1, 3, and 5 are "bad".

For each "bad" column, build a vector with a $-1$ in the corresponding slot, and zeros in all the other "bad column" slots. For instance, for our example, the bad columns are 1,3, 5 so we'd build

$$\begin{bmatrix} -1 \\ * \\ 0 \\ * \\ 0 \end{bmatrix} \begin{bmatrix} 0 \\ * \\ -1 \\ * \\ 0 \end{bmatrix} \begin{bmatrix} 0 \\ * \\ 0 \\ * \\ -1 \end{bmatrix}$$ For each of these, fill in, as the missing entries, the numbers from the corresponding column of $M$. So for the first, we'd fill in with $0$ and $0$; for the second, we'd use $2$ and $0$; for the third, we'd use $3$ and $4$. The result is $$\begin{bmatrix} -1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 0 \\ 2 \\ -1 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 0 \\ 3 \\ 0 \\ 4 \\ -1 \end{bmatrix}$$

These vectors are then put into the columns of a matrix $A$; picking $b = 0$ gives you the answer you need.