This is a problem from an olympiad I took today. I tried but couldn't solve it.

Let $A$ and $B$ rectangular matrices with real entries, of dimensions $k\times n$ and $m\times n$ respectively. Prove that if for every $n\times l$ matrix $X$ ($l\in \mathbb{Z}^+$) the equality $AX=0$ implies $BX=0$, then there exists a matrix $C$ such that $B=CA$.

I tried to define a commutative diagram, but failed. Anyhow, I'd prefer a solution that works with the matrices explicitly. But I'll welcome and appreciate any solutions.

-

$AX=0$ means that the rows of $A$ are all orthogonal to the columns of $X$, and likewise for $BX=0$. $B=CA$ means that the rows of $B$ are linear combinations of the rows of $A$.

Assume that there is a row of $B$ that is not a linear combination of the rows of $A$. Orthogonalize that row to the rows of $A$, and choose $X$ as the column vector corresponding to this orthogonalized row. Then $AX=0$, but $BX\neq0$. Hence the rows of $B$ are linear combinations of the rows of $A$.

-
Sorry, what do you mean by "orthogonalize that row to the rows of $A$" ? –  kevincuadros Feb 5 '11 at 23:24
@joriki: I'm not really grasping your solution, could you elaborate a little? Specially the last 2 lines. –  kevincuadros Feb 5 '11 at 23:30
The rows of A span a vector space R (of row vectors). Every row vector b can be written as the sum of an element b_r of R and an element b_c of its orthogonal complement. If a row b of B is not a linear combination of the rows of A and you write it in this form, then b_c will necessarily be non-zero. By orthogonalizing to the rows of A, I mean dropping b_r and keeping only b_c. This is orthogonal to all rows of A but not orthogonal to b, since b_c * b = b_c * (b_r + b_c) = b_c * b_c != 0. Thus if you choose X as the corresponding column vector, AX = 0, but BX != 0. Hope that makes it clearer? –  joriki Feb 5 '11 at 23:46
@joriki: I think I get it now. –  kevincuadros Feb 7 '11 at 23:38
@joriki: aren't the rows of $B$ linear combinations of the columns of A? –  Weltschmerz Mar 2 '11 at 13:03

Think of $A$ as a linear transformation from $\mathbb{R}^n$ to $\mathbb{R}^k$, and $B$ as a linear transformation from $\mathbb{R}^n$ to $\mathbb{R}^m$. White $L_M$ for the linear transformation defined by multiplication by the matrix $M$.

For the matrix $C$ to exist, you must have a linear transformation $L$ from $\mathbb{R}^k$ to $\mathbb{R}^m$ such that $L\circ L_A = L_B$. Then you can define $C$ to be the standard matrix representation of $L$.

A necessary condition for this to be possible is that $\mathbf{N}(L_A) \subseteq \mathbf{N}(L_B)$ (if there is $\mathbf{v}\in\mathbf{N}(L_A)$ that is not in $\mathbf{N}(L_B)$, then $L\circ L_A(\mathbf{v})=\mathbf{0}\neq L_B(\mathbf{v})$ and you're sunk).

In fact, this is sufficient: find a basis $\mathbf{v}_1,\ldots,\mathbf{v}_s$ for the nullspace of $A$, and then extend it to a basis for $\mathbb{R}^n$, $\mathbf{v}_{s+1},\dots,\mathbf{v}_n$. Note that the image of $\mathbf{v}_{s+1},\ldots,\mathbf{v}_n$ in $\mathbb{R}^k$ under $L_A$ is linearly independent (this is essentially the Rank-Nullity Theorem), so you can complete $A\mathbf{v}_{s+1},\ldots,A\mathbf{v}_n$ to a basis $\mathbf{w}_1,\ldots,\mathbf{w}_{(k-n+s)}$ of $\mathbb{R}^k$. Define $L\colon\mathbb{R}^k\to\mathbb{R}^n$ by letting $L(A\mathbf{v}_j) = B\mathbf{v}_j$ for $j=s+1,\ldots,n$, and arbitrarily for $\mathbf{w}_i$. Then let $C$ be the standard matrix for this linear transformation.

-
Shouldn't it be a linear transformation from $\mathbb{R}^k$ to $\mathbb{R}^m$ such that $L_C \circ L_A = L_B$? –  PEV Feb 5 '11 at 22:56
@PEV: Yes, thanks. –  Arturo Magidin Feb 5 '11 at 22:59