A matrix completion problem

Question

I need to find an algorithm (if it exists) of the following matrix completion problem.

I need to construct $n^2$ positive semi-definite matrices, say $\{P_i\}_{i=1}^n$. Entries of these matrices are complex numbers.

1. Each matrices are of dimension $n^2\times n^2$.

2. I only know the $n\times n$ block at top left corner of each matrix.

3. $P_i$ is a projection operator. For time being, let us assume that they are of rank $1$ for all $i$. Moreover they are mutually orthonormal.

4. $\sum_{i=1}^{n^2}P_i=I_{n^2}$ is the identity operator.

I do not know much about the matrix completion problem, and it may not be profitable for me to go through the vast literature to find nothing. Hence I request everyone to inform me about any such paper/ algorithm which deals with this specific problem (or something close to this). Advanced thanks for any help suggestion. Please feel free to retag the question (or move to the tcs section) if you think it is necessary.

Answer 1

Let $m=n^2$. You are looking for an orthonormal basis $(u_i : i=1,\dots,m)$ of $m$-dimensional space, such that for every $i$ the orthogonal projection onto $u_i$ has the prescribed upper-left corner of size $n\times n$. For this to be possible, each such corner must be a symmetric matrix of rank $1$ with norm at most one. Equivalently, each corner is of the form $v_i\otimes v_i$ for some $n$-dimensional vector $v_i$ with norm at most $1$. You can find $v_i$ (up to $\pm$ sign, which is immaterial) from the corner matrix by taking the first column and dividing it by the square root of the diagonal entry in that column.

Arrange $v_1,\dots,v_m$ as columns of an $n\times m$ matrix $V$. Each vector $u_i$ must have the same first $n$ coordinates as $v_i$. Therefore, we are looking for a way to complete $V$ to an orthogonal $m\times m$ matrix $U$. Recall that a matrix is orthogonal if and only if its rows are orthonormal. Therefore, the rows of $V$ must form an orthonormal set. This is the necessary and sufficient condition for the existence of desired completion. Indeed, if the rows of $V$ are orthonormal, we can extend them to an orthonormal basis of the entire space pretty easily -- throw in the standard basis vectors $e_i$, apply the Gram-Schmidt algorithm, and discard any vectors that the algorithm turns into zero.

Once $U$ is obtained, its columns give you the vectors $u_i$ that you are looking for. The projection matrices themselves are $P_i=u_i\otimes u_i$.

Example: $n=2$, the given corners are $$\begin{pmatrix} 1/4 & 1/4 \\ 1/4 & 1/4 \end{pmatrix}, \ \begin{pmatrix} 1/4 & 1/4 \\ 1/4 & 1/4 \end{pmatrix}, \ \begin{pmatrix} 1/4 & -1/4 \\ -1/4 & 1/4 \end{pmatrix}, \ \begin{pmatrix} 1/4 & -1/4 \\ -1/4 & 1/4 \end{pmatrix}$$ Then $$v_1=v_2=\begin{pmatrix} 1/2 \\ 1/2 \end{pmatrix}, \ \ \ \ v_3=v_4=\begin{pmatrix} 1/2 \\ -1/2 \end{pmatrix}$$ Hence
$$V =\begin{pmatrix} 1/2 & 1/2 & 1/2 & 1/2 \\ 1/2 & 1/2 & -1/2 & -1/2 \end{pmatrix} $$ Since the rows are orthonormal, the desired completion exists. For example, $$ U =\begin{pmatrix} 1/2 & 1/2 & 1/2 & 1/2 \\ 1/2 & 1/2 & -1/2 & -1/2 \\ 1/2 & -1/2 & 1/2 & -1/2 \\ -1/2 & 1/2 & 1/2 & -1/2 \end{pmatrix} $$