DaftWulie's answer to Extending a square matrix to a Unitary matrix says that extending a matrix into a unitary cannot be done unless there's constraints on the matrix. What are the constraints?
3 Answers
A necessary and sufficient condition is that, given an $n\times n$ matrix $M$, you can construct a $2n\times 2n$ unitary matrix $U$ provided the singular values of $M$ are all upper bounded by 1.
Sufficiency
To see this, express the singular value decomposition of $M$ as $$ M=RDV $$ where $D$ is diagonal and $R$, $V$ are unitary. Now define $$ U=\left(\begin{array}{cc} M & R\sqrt{\mathbb{I}-D^2}V \\ R\sqrt{\mathbb{I}-D^2}V & -M \end{array}\right), $$ which we can only do if the singular values are no larger than 1. Let's verify that it's unitary \begin{align*} UU^\dagger&=\left(\begin{array}{cc} RDV & R\sqrt{\mathbb{I}-D^2}V \\ R\sqrt{\mathbb{I}-D^2}V & -RDV \end{array}\right)\left(\begin{array}{cc} V^\dagger DR^\dagger & V^\dagger\sqrt{\mathbb{I}-D^2}R^\dagger \\ V^\dagger\sqrt{\mathbb{I}-D^2}R^\dagger & -V^\dagger DR^\dagger \end{array}\right) \\ &=\left(\begin{array}{cc} RD^2R^\dagger+R(\mathbb{I}-D^2)R^\dagger & 0 \\ 0 & RD^2R^\dagger+R(\mathbb{I}-D^2)R^\dagger \end{array}\right) \\ &=\mathbb{I}. \end{align*}
Necessity
Imagine I have a matrix $M$ with a singular value $\lambda>1$ and corresponding normalised vector $|\lambda\rangle$. Assume I construct a unitary $$ U=\left(\begin{array}{cc} M & A \\ B & C \end{array}\right). $$ Let's act $U$ on the state $\left(\begin{array}{c} |\lambda\rangle \\ 0 \end{array}\right)$. We get $$ U\left(\begin{array}{c} |\lambda\rangle \\ 0 \end{array}\right)=\left(\begin{array}{c} M|\lambda\rangle \\ B|\lambda\rangle \end{array}\right). $$ This output state must have a norm that is at least the norm of $M|\lambda\rangle$, i.e. $\lambda>1$. But if $U$ is a unitary, the norm must be 1. So it must be impossible to perform such a construction if there exists a singular value $\lambda>1$.
-
1$\begingroup$ @DaftWulie: This is "a" necessary and sufficient condition. Is it the only one? $\endgroup$ Jan 10, 2019 at 17:54
-
1$\begingroup$ You might be able to phrase the condition in another way, but it would be materially equivalent. That’s the point of necessary and sufficient - it is the precise categorisation of what is required. $\endgroup$ Jan 10, 2019 at 18:24
-
1$\begingroup$ "A necessary and sufficient condition is that, given an n×n matrix M, you can construct a 2n×2n unitary matrix U provided the singular values of M are all upper bounded by 1." If I'm reading this correctly (and I am far from sure I am), it seems that this can be rewritten as "Given a matrix $M$, a necessary and sufficient condition for being able to extend $M$ to a 2n×2n unitary matrix is that the singular values of $M$ all be less than or equal to $1$." $\endgroup$ Jan 10, 2019 at 19:31
-
1$\begingroup$ @DaftWullie it is definitely possible to do this with less then doubling the space though. As a trivial example, any matrix obtained by removing one row and column from a unitary matrix can be extended to a unitary matrix by adding a single dimension. Do you have any idea on how one could estimate the minimum number of dimensions that have to be added to a given matrix to make it into a unitary? $\endgroup$– glS ♦Jan 11, 2019 at 9:42
-
$\begingroup$ @glS Well, I know what I'd do, which is perform a Gram-Schmidt-like procedure, extending one row at a time, ensuring orthonormality with all previous rows. I don't know ho to succinctly write down the dimension number based on properties of $M$ - I've never thought about it. I guess a starting point is by counting the number of singular values equal to 1, and reducing the size of the extension by that much? $\endgroup$ Jan 11, 2019 at 9:56
$\newcommand{\bs}[1]{\boldsymbol{#1}}$Here is a slightly different way to prove what the other excellent answer did.
Note that a matrix $U$ is unitary if and only if it sends orthonormal bases into orthonormal bases. This, in particular, means that if $U$ is unitary then $\|U\bs v\|=1$ for any $\bs v$ with $\|\bs v\|=1$.
Let us write the SVD of $M$ as $M\bs u_k=s_k\bs v_k$, where $s_k\ge0$ are the singular values of $M$.
Note that if $U$ is an extension of $M$, then $U\bs u_k=s_k \bs v_k+\bs w_k$ for some $\bs w_k$ orthogonal to $\bs v_k$ (and more generally to the whole range of $M$).
If follows that if, for any $k$, $s_k>1$, then $\|U\bs u_k\|>1$, and thus $U$ is not unitary.
On the other hand, if $s_k\le1$ for all $k$, let us show how can always construct a unitary $U$ that contains $M$ as a submatrix. Let us denote with $\bs v\oplus \bs 0$ the vectors in the extended $2n$-dimensional space that are built by appending zeros to the $n$-dimensional vector $\bs v$, and with $\bs 0\oplus\bs v$ the vectors that are equal to $\bs v$ in the last $n$ dimensions by zero in the first $n$ ones. Being $\{\bs u_k\}_k$ a basis for the original space, it follows that $\{\bs u_k\oplus \bs 0,\bs0\oplus\bs u_k\}_k$ is a basis for the extended space.
We will define $U$ through its action on the vectors $u_k\oplus \bs 0$ and $\bs0\oplus u_k$ as follows: \begin{align} U(\bs u_k\oplus \bs 0)&=s_k(\bs v_k\oplus\bs 0)+\sqrt{1-s_k^2}(\bs 0\oplus \bs v_k) \\ U(\bs0 \oplus \bs u_k)&=\sqrt{1-s_k^2}(\bs v_k\oplus\bs 0)-s_k(\bs 0\oplus \bs v_k). \end{align}
One can then check that all of these output vectors form an orthonormal system in the extended space, and thus $U$ is unitary.
-
$\begingroup$ $\newcommand{\bs}[1]{\boldsymbol{#1}}$ Let us denote with $\bs v\oplus \bs 0$ the vectors in the extended $2n$-dimensional space that are built by appending zeros to the $n$-dimensional vector $\bs v$, and with $\bs 0\oplus\bs v$ the vectors that are equal to $\bs v$ in the last $n$ dimensions by zero in the first $n$ ones @gls sorry, can you show the example vector for $\bs 0\oplus\bs v$ ? it sounded like same as the other $\endgroup$ Jun 30, 2021 at 19:35
-
$\begingroup$ an example for $n=2$ would be $(0,0,1,1)$ (without worrying about normalisation) $\endgroup$– glS ♦Jun 30, 2021 at 20:10
Here's a solution that follows a slightly different idea, but provides the precise number of rows that need to be added to get a unitary matrix.
Let $M$ be an arbitrary $n\times m$ matrix. As a first observation, note that the task of adding rows/columns can be reduced to that of adding rows to get $m$ orthonormal columns. Indeed, once this is done, we get an isometry, which one can then trivially make into a unitary by simply building an orthonormal basis from the orthonormal columns in the usual way (Gram-Schmidt etc).
We thus want to figure out when it is possible to add rows to $M$ to obtain orthonormal columns, and when it is possible, exactly how many rows need to be added. Call $S$ the block of rows added to $M$. If we are adding $s$ rows, then $S$ is an $s\times m$ matrix. Note that the full ($M$ with $S$ added) matrix is an isometry iff $$M^\dagger M + S^\dagger S = I_{m\times m} \Longleftrightarrow S^\dagger S = I_{m\times m}-M^\dagger M.$$ Now, thinking in terms of SVDs, observe how this means that this is possible iff the singular values of $M$ are all in the range $[0,1]$. Furthermore, we can now also say that the singular values of $S$, call these $s_k$, must be $s_k=\sqrt{1-m_k^2}$, with $m_k$ the singular values of $M$.
In summary, we found that $S$ must be a matrix whose singular values are $\sqrt{1-m_k^2}$. More precisely, multiplicity needs to be also matched here: e.g. if $M$ has a two-fold degenerate singular value $0.5$, then $S$ needs to have a two-fold degenerate singular value $\sqrt{1-0.5^2}$.
This is telling us that $S$ needs to have rank equal to that of $I-M^\dagger M$, or in other words, $S$ needs to have a number of rows equal to the number of nonzero singular values of $M$. This is both necessary and sufficient, and once verified, building $S$ can be done taking as right singular vectors those of $M$ with nonzero singular values, and as left singular vectors an arbitrary orthonormal set in the relevant space.
As an easy sanity check, try taking an arbitrary set of orthonormal columns in whatever (sufficiently large) dimension you like. Observe how removing $k$ rows from the corresponding matrix, $I-M^\dagger M$ has precisely $k$ vanishing eigenvalues, implying that precisely $k$ rows need to be added to $M$ to get back an isometry.
-
$\begingroup$ sorry. one more question as I am new here "Furthermore, we can now also say that the singular values of $S$, call these $s_k$, must be $s_k=\sqrt{1-m_k^2}$, with $m_k$ the singular values of $M$" Could you kindly point to me why? $\endgroup$ Jun 30, 2021 at 19:44
-
$\begingroup$ because (1) the square of the singular values of a matrix $A$ are equal to the eigenvalues of $A^\dagger A$, and (2) $I-A$ has the same eigenvalues as $A$ $\endgroup$– glS ♦Jun 30, 2021 at 20:08
-
$\begingroup$ thanks. I understood (1) but (2) I-A case, doesn't the sum of eigenvalues increase by 2n from A (assuming I is nxn matrix) due to I ? $\endgroup$ Jun 30, 2021 at 20:48
-
$\begingroup$ @JohnParker indeed, you are right. The eigenvalues of $I$ and $I-A$ are obviously different, I meant to say that they have the same eigenvectors $\endgroup$– glS ♦Jul 1, 2021 at 10:38
-
$\begingroup$ thank you. I kinda guessed it but again appreciate it! $\endgroup$ Jul 1, 2021 at 13:25