A question on a certain block decomposition of semi-definite matrices. Let $m,n\in\mathbb{N}$, with $m,n>1$. Suppose $K\in \mathbb{M}_{mn\times mn}(\mathbb{C})$ is positive semidefinite. We can always write
$$K=\sum_{i,j=1}^m E_{i,j}\otimes K_{i,j},$$
for some collection of matrices $K_{i,j}\in \mathbb{M}_{n\times n}(\mathbb{C}) $, where $E_{i,j}\in \mathbb{M}_{m\times m}(\mathbb{C})$ is the matrix with 1 in the  entry $(i,j)$ and zeros everywhere else. This amounts to writing $K$ in the block diagonal form
$$\begin{pmatrix}
K_{1,1} &\dots  &K_{1,m} \\ 
 \vdots &\ddots  &\vdots \\ 
 K_{m,1}& \dots & K_{m,m}
\end{pmatrix}$$.
Under what conditions can we find a collection of non-square matrices $A_k\in \mathbb{M}_{mn\times n}(\mathbb{C})$ such that $K_{i,j}=A_i^*A_j$ for all $i,j\in \{1,\dots,m \}$? 
In other words, when can we write 
$$K=\begin{pmatrix}
A_1^*A_1 &\dots  &A_1^*A_m \\ 
 \vdots &\ddots  &\vdots \\ 
 A_m^*A_1& \dots & A_m^*A_m
\end{pmatrix}=\begin{pmatrix}
A^*_{1}\\ 
\vdots\\ A^*_{m}\end{pmatrix}
\begin{pmatrix}
A_{1} &\dots  &A_{m} 
\end{pmatrix}$$
for some collection of matrices $A_k\in \mathbb{M}_{mn\times n}(\mathbb{C})$?
 A: You can always find those matrices $A_k$. Since $K$ is positive, there exists $B\in M_{mn}(\mathbb C)$ such that $K=B^*B$. Now, writing $B$ in the same block form as $K$,  let 
$$
A_k=\begin{bmatrix}B_{1k}\\ B_{2k}\\ \vdots \\ B_{mk}\end{bmatrix}.
$$
Then 
$$
K_{ij}=\sum_{h=1}^m (B^*)_{ih}B_{hj}=\sum_{h=1}^mB_{hi}^*B_{hj}=A_i^*A_j^*.
$$

(this below was the answer to the original form of the question, which received upvotes and has some value, so I'm leaving it)
Note that if $K$ is of the form you want, the eigenvalues of $K$ are the same (bar zeroes) to those of 
$$
\begin{bmatrix}A_1&\cdots&A_m\end{bmatrix}\begin{bmatrix}A_1^*\\ \vdots \\A_m^*\end{bmatrix} =A_1A_1^*+\cdots+A_mA_m^*,
$$
an $mn\times mn$ matrix. So $K$ has at most $mn$ distinct eigenvalues, which discards many possible $K$. 
What happens in general is that $K$ is a sum of matrices of that form. Since $K$ is positive semidefinite, there exists $B$, with blocks the same size as those of $K$, such that $K=BB^*$. Now let 
$$
B_k=
\begin{bmatrix}
0&\cdots&0&B_{k1}&0\cdots&0\\
0&\cdots&0&B_{k2}&0\cdots&0\\
0&\cdots&0&\vdots&0\cdots&0\\
0&\cdots&0&B_{km}&0\cdots&0\\
\end{bmatrix}.
$$
Then, as $B_jB_k^*=0$ if $j\ne k$,
$$
K=BB^*=\sum_{k=1}^m B_k\sum_{k=1}^mB_k^*=\sum_{k=1}^mB_kB_k^*
=\sum_{k=1}^m\begin{bmatrix}B_{k1}\\ \vdots\\ B_{km}\end{bmatrix}
\begin{bmatrix}B_{k1}^*&\cdots& B_{km}^*\end{bmatrix}.
$$
Now you can take $A_{kj}=B_{kj}^*$. 
A: Actually the answer turns out to be trivial. Since $K$ is positive semidefinite, we can write $K=B^*B$ for some $B\in \mathbb{M}_{mn\times mn}(\mathbb{C})$. Write
$$B=\begin{pmatrix}
B_{11} & \dots &B_{1m} \\ 
 \vdots& \ddots &\vdots \\ 
 B_{m1}&\dots  &B_{mm} 
\end{pmatrix},$$
and let
$$A_{k}=\begin{pmatrix}
B_{1k}\\ 
\vdots\\ 
B_{mk}
\end{pmatrix}\in \mathbb{M}_{mn\times n}(\mathbb{C}).$$
Then
$$B=\begin{pmatrix}
A_1 &\dots  &A_m 
\end{pmatrix}\quad\quad B^*=\begin{pmatrix}
A_1^*\\\vdots 
\\A_m^* 
\end{pmatrix},$$
and
$$K=B^*B=\begin{pmatrix}
A_1^*\\\vdots 
\\A_m^* 
\end{pmatrix}\begin{pmatrix}
A_1 &\dots  &A_m 
\end{pmatrix}$$
