rank of $A \otimes B$ For two matrices $A$ and $B$, what would be the rank of $A\otimes B$ as a matrix?
Seems to me that $rank(A\otimes B) = rank(A)\cdot rank(B)$. But I don't see an elegant proof... 
 A: Every $m\times n$ matrix $A$ can be reduced, via elementary row/column operations, to the form $D=\operatorname{diag}(I_r,\ 0_{(m-r)\times(n-r)})$, where $r=\operatorname{rank}(A)$. That is, $A=PDQ$ for some invertible matrices $P$ and $Q$. So, $A\otimes B$ can be rewritten in the form of
$$
A\otimes B
=(P_1D_1Q_1)\otimes (P_2D_2Q_2)
=(P_1\otimes P_2)(D_1\otimes D_2)(Q_1\otimes Q_2).
$$
As $P_1\otimes P_2$ and $Q_1\otimes Q_2$ are invertible (their inverses are $P_1^{-1}\otimes P_2^{-1}$ and $Q_1^{-1}\otimes Q_2^{-1}$), they preserve rank. Therefore $\operatorname{rank}(A\otimes B)=\operatorname{rank}(D_1\otimes D_2)$. Now, for diagonal matrices, I think the statement is obvious enough.
A: Approach 1 (with matrices). We will use the identity $(XY)\otimes(ZT) = (X \otimes Z)(Y \otimes T)$ which holds for all matrices $X, Y, Z, T$ of suitable size. Notice that from this identity it follows that $X \otimes Y$ is invertible if both $X$ and $Y$ are invertible.
Moving on to the problem. It is known that matrix $A$ can be represented as $A_l A_d A_r$, where $A_l$ and $A_r$ are invertible of appropriate sizes, and $A_d$ has $\mathrm{rank}(A)$ $1$'s on the main diagonal and $0$'s everywhere else. In a similar fashion, represent $B$ as $B_l B_d B_r$. Now we have
$$
A \otimes B = (A_l \otimes B_l)(A_d \otimes B_d)(A_r \otimes B_r).
$$
Matrices $A_l \otimes B_l$ and $A_r \otimes B_r$ are invertible, and $A_d \otimes B_d$ has $\mathrm{rank}(A)\cdot\mathrm{rank}(B)$ 1's on the main diagonal and 0's everywhere else. It is clear then that $\mathrm{rank}(A \otimes B) = \mathrm{rank}(A) \mathrm{rank}(B)$.
Approach 2 (with linear maps). In the language of linear maps, we have two linear maps $f_1: L_1 \to R_1$ and $f_2: L_2 \to R_2$ and their tensor product $f_1 \otimes f_2: L_1 \otimes L_2 \to R_1 \otimes R_2$. We want to show that $\mathrm{rank}(f_1 \otimes f_2) = \mathrm{rank}(f_1) \mathrm{rank}(f_2)$.
Lemma 1. If $f_i$, $g_i$ are linear maps between appropriate spaces, then $$(f_1 \otimes f_2)(g_1 \otimes g_2) = (f_1 g_1) \otimes (f_2 g_2).$$
This follows straight from the definition of the tensor product of maps.
Lemma 2. A linear map $f: L \to R$ is injective iff there is a linear map $g: R \to L$ such that $g f = \mathrm{id}_L$. $f$ is surjective iff there is a linear map $g: R \to L$ such that $f g = \mathrm{id}_R$.
This is an easy exercise.
Corollary 1. If linear maps $f_1: L_1 \to R_1$ and $f_2: L_2 \to R_2$ are injective, so is $f_1 \otimes f_2$.
Proof. By lemma 2, there exist linear maps $g_1: R_1 \to L_1$ and $g_2: R_2 \to L_2$ such that $g_1 f_1 = \mathrm{id}_{L_1}$ and $g_2 f_2 = \mathrm{id}_{L_2}$. From lemma 1 we have
$$
(g_1 \otimes g_2)(f_1 \otimes f_2) = (g_1 f_1) \otimes(g_2 f_2) = \mathrm{id}_{L_1}\otimes \mathrm{id}_{L_2} = \mathrm{id}_{L_1 \otimes L_2}.
$$
Using lemma 2 again we see that $f_1 \otimes f_2$ is injective, qed.
Corollary 2. If linear maps $f_1: L_1 \to R_1$ and $f_2: L_2 \to R_2$ are surjective, so is $f_1 \otimes f_2$.
The proof is similar to corollary 1.
Now we are ready to prove that $\mathrm{rank}(f_1 \otimes f_2) = \mathrm{rank}(f_1) \mathrm{rank}(f_2)$. It is known that there exist vector spaces $M_i$ and maps $g_i: L_i \to M_i$, $h_i: M_i \to R_i$ such that $f_i = h_i g_i$, $g_i$ are surjective, $h_i$ are injective, and $\dim M_i = \mathrm{rank}(f_i)$, for every $i = 1, 2$.
Now we have maps $g_1 \otimes g_2: L_1 \otimes L_2 \to M_1 \otimes M_2$ and $h_1 \otimes h_2 : M_1 \otimes M_2 \to R_1 \otimes R_2$. By corollaries 1 and 2 the former map is surjective and the latter is injective. Now, since $f_1 \otimes f_2 = (h_1 \otimes h_2)(g_1 \otimes g_2)$, we see that its rank is equal to the dimension of the "middle space", i.e.:
$$
\mathrm{rank}(f_1 \otimes f_2) = \dim M_1 \otimes M_2 = (\dim M_1)(\dim M_2) = \mathrm{rank}(f_1)\mathrm{rank}(f_2),
$$
qed.
