Explain why any vector $x$ in the row space of $A$ can be written as $x = A^Ty$ for some vector $y$ In the process of solving a larger problem I have been asked to show why any vector $x$ in the row space of $A$ can be written as $x = A^Ty $ for some vector $y$. I get the feeling this is simpler than it seems but I can't seem to wrap my head around how this works.
 A: If $e_i$ is the $i$th vector of the canonical basis, them $A^T.e_i$ is the $i$th column of $A^T$, and therefore the $i$th row of $A$.
So, if the rows of $A$ are $r_1,r_2,\ldots,r_k$ and if $\alpha_1,\alpha_2,\ldots,\alpha_k$, are scalars, then$$\alpha_1r_1+\alpha_2r_2+\cdots+\alpha_kr_k=A^T.(\alpha_1e_1+\alpha_2e_2+\cdots+\alpha_ke_k).$$
A: A somewhat hand-wavy explanation:  
Several useful interpretations of a matrix product can be obtained by grouping in various ways. For instance, by taking horizontal slices through the matrix $M$, the elements of the product $M\mathbf y$ of this matrix with a column vector $\mathbf y$ can be interpreted as dot products of $\mathbf y$ with each row of $M$.  
Here, we instead take vertical slices through $M$, which lets us interpret the product $M\mathbf y$ as a linear combination of the columns of $M$. You can arrive at this directly from the basic definition of matrix multiplication, or by expanding $\mathbf y=(y_1,\dots,y_n)^T = y_1\mathbf e_1+\cdots+y_n\mathbf e_n$, using linearity and noting that $M\mathbf e_j$ is equal to the $j$th column of $M$, $\mathbf m_j$, so that $M\mathbf y = y_1\mathbf m_1+\cdots+y_n\mathbf m_n$.  
Thus, $A^T\mathbf y$ is a linear combination of the columns of $A^T$, but the columns of $A^T$ are the rows of $A$. Now, every element $\mathbf x$ of the row space of $A$ is a linear combination $y_1\mathbf A_1+\cdots+y_n\mathbf A_n$ of the rows $\mathbf A_i$ of $A$; collecting the coefficients into a vector $\mathbf y$ produces the desired identity.
