# Probability distributions consistent with a mixed state

## I Introduction

The density matrix was introduced  as a means of describing a quantum system when the state of the system is not completely known. In particular, if the state of the system is $`|\psi _i`$ with probability $`p_i`$, then the density matrix is defined by

$`\rho {\displaystyle \underset{i}{}}p_i|\psi _i\psi _i|.`$ (1)   
For a fixed density matrix it is natural to ask what class of ensembles $`\{p_i,|\psi _i\}`$ gives rise to that density matrix? This problem was addressed by Scrödinger , whose results have been extended by Jaynes , and by Hughston, Jozsa, and Wootters . The result of these investigations, the classification theorem for ensembles, has been of considerable utility in quantum statistical mechanics, quantum information theory, quantum computation, and quantum error-correction.

In this paper we use the classification theorem for ensembles to obtain an explicit classification of probability distributions $`(p_i)`$ such that there exist pure states $`|\psi _i`$ satisfying $`\rho =_ip_i|\psi _i\psi _i|`$, for some fixed density matrix $`\rho `$. This is done in Section II. Section III illustrates the result with several simple applications to quantum mechanics and quantum information theory. Section IV concludes the paper.

## II Probability distributions consistent with a mixed state

To state and prove our results we need to introduce some notions from the theory of majorization . Majorization is an area of mathematics concerned with the problem of comparing two vectors to determine which is more “disordered”. Suppose $`x`$ and $`y`$ are two $`d`$-dimensional real vectors. Then we say $`x`$ is majorized by $`y`$, written $`xy`$, if

$`{\displaystyle \underset{i=1}{\overset{k}{}}}x_i^{}{\displaystyle \underset{i=1}{\overset{k}{}}}y_i^{}`$ (2)   
for $`k=1,\mathrm{},d1`$, with strict equality required when $`k=d`$. The  notation indicates that the vector components are to be ordered into decreasing order. The usual interpretation is that $`x`$ is more “disordered” or “mixed” than $`y`$. When $`x`$ and $`y`$ are probability distributions it can be shown that $`xy`$ implies many quantities commonly used as measures of disorder, such as the Shannon entropy, are never lower for $`x`$ than for $`y`$.

There is a close relation between unitary matrices and majorization. Any matrix $`D`$ whose components may be written in the form $`D_{ij}=|u_{ij}|^2`$ for some unitary matrix $`u=(u_{ij})`$ is said to be unitary-stochastic. The following theorem  connects the unitary-stochastic matrices to majorization.

Theorem 1: Let $`x`$ and $`y`$ be $`d`$-dimensional vectors. Then $`xy`$ if and only if there exists unitary-stochastic $`D`$ such that $`x=Dy`$.

The proof of this theorem  is constructive in nature. That is, given $`xy`$ it is possible to explicitly construct a unitary matrix $`u=(u_{ij})`$ such that $`x=Dy`$ where $`(D_{ij})=(|u_{ij}|^2)`$. Indeed, even more is true — for the forward implication in Theorem 1 it turns out to be sufficient to consider only orthogonal matrices $`u`$, that is, real matrices satisfying $`uu^T=u^Tu=I`$, where <sup>T</sup> is the transpose operation. The corresponding matrix $`D_{ij}=u_{ij}^2`$ is known as an ortho-stochastic matrix. Note that the expression $`u_{ij}^2`$ indicates the square of the $`ij`$th component of the matrix $`u`$, not the $`ij`$th component of $`u^2`$. The Appendix to this paper gives an outline of the construction needed for the reverse implication in Theorem 1, somewhat different to the proof in .

The second result we need is the classification theorem for ensembles :

Theorem 2: Let $`\rho `$ be a density matrix. Then $`\{p_i,|\psi _i\}`$ is an ensemble for $`\rho `$ if and only if there exists a unitary matrix $`u=(u_{ij})`$ such that

$`\sqrt{p_i}|\psi _i={\displaystyle \underset{j}{}}u_{ij}|e_j,`$ (3)   
where $`|e_j`$ are eigenvectors of $`\rho `$ normalized so that $`\lambda _j^\rho =e_j|e_j`$ are the corresponding eigenvalues.

In the statement of Theorem 2 it is understood that there may be more elements in the ensemble $`\{p_i,|\psi _i\}`$ than there are eigenvectors $`|e_j`$. When this is the case one appends extra zero vectors to the list of eigenvectors, until the number of elements in the two lists matches. Combining Theorem 1 and Theorem 2 in an appropriate way gives the following classification theorem for the class of probability distributions consistent with a given density matrix:

Theorem 3: Suppose $`\rho `$ is a density matrix. Let $`(p_i)`$ be a probability distribution. Then there exist normalized quantum states $`|\psi _i`$ such that

$`\rho ={\displaystyle \underset{i}{}}p_i|\psi _i\psi _i|`$ (4)   
if and only if $`(p_i)\lambda ^\rho `$, where $`\lambda ^\rho `$ is the vector of eigenvalues of $`\rho `$.

In the statement of Theorem 3 it is understood that if the vector $`(p_i)`$ contains more elements than the vector $`\lambda ^\rho `$, then one should append sufficiently many zeros to $`\lambda ^\rho `$ that the two vectors be of the same length.

Proof of Theorem 3:

Suppose there exists a set of states $`|\psi _i`$ such that $`\rho =_ip_i|\psi _i\psi _i|`$. By Theorem 2 equation (3) must hold. Multiplying (3) by its adjoint gives

$`p_i={\displaystyle \underset{jk}{}}u_{ik}^{}u_{ij}\lambda _j^\rho \delta _{jk},`$ (5)   
which simplifies to

$`p_i`$ $`=`$ $`{\displaystyle \underset{j}{}}|u_{ij}|^2\lambda _j^\rho .`$ (6)   
Setting $`D_{ij}|u_{ij}|^2`$, we have $`(p_i)=D\lambda ^\rho `$ for unitary-stochastic $`D`$, and by Theorem 1, $`(p_i)\lambda ^\rho `$.

Conversely, if $`(p_i)\lambda ^\rho `$ then by Theorem 1 we can find unitary $`u`$ such that (6) is satisfied. Now define states $`|\psi _i`$ by Equation (3); since $`u_{ij},p_i`$ and $`|e_j`$ are known this equation determines the $`|\psi _i`$ uniquely. By Theorem 2 we need only check that these are properly normalized pure states to complete the proof. Multiplying the definition of $`|\psi _i`$, Equation (3), by its adjoint gives

$`p_i\psi _i|\psi _i`$ $`=`$ $`{\displaystyle \underset{jk}{}}u_{ij}u_{ik}^{}e_k|e_j`$ (7)   
$`=`$ $`{\displaystyle \underset{j}{}}|u_{ij}|^2\lambda _j^\rho `$ (8)   
$`=`$ $`p_i,`$ (9)   
where the last step follows from the choice of $`u`$ to satisfy (6). It follows that $`|\psi _i`$ is a normalized pure state.

QED

Theorem 3 is the central result of this paper. Many elements of the proof are already implicit in the paper of Hughston, Jozsa and Wootters , however they do not explicitly draw the connection with majorization. The forward implication has been proved by Uhlmann , who conjectured but did not find an explicit construction for the reverse implication.

## III Applications

The remaining sections of this paper demonstrate several illustrative applications of Theorem 3 to elementary quantum mechanics and quantum information theory.

### A Uniform ensembles exist for any density matrix

As our first application of Theorem 3, suppose $`d`$ is the rank of $`\rho `$, and that $`md`$. Then it is easy to verify that $`(1/m,1/m,\mathrm{},1/m)\lambda ^\rho `$, and therefore there exist pure states $`|\psi _1,\mathrm{},|\psi _m`$ such that $`\rho `$ is an equal mixture of these states with probability $`1/m`$,

$`\rho ={\displaystyle \underset{i}{}}{\displaystyle \frac{|\psi _i\psi _i|}{m}}.`$ (10)   
Indeed, if we choose $`md`$ where $`d`$ is the dimension of the underlying space, then for any $`\rho `$ there exists a set of states such that (10) holds. A priori it is not at all obvious that such a set of pure states should exist for any density matrix $`\rho `$, however Theorem 3 guarantees that this is indeed the case: any density matrix may be regarded as the result of picking uniformly at random from some ensemble of pure states.

### B Schur-convex functions of ensemble probabilities

A second application of Theorem 3 relates functions of the eigenvalues of $`\rho `$ to functions of the probabilities $`(p_i)`$. The theory of isotone functions  is concerned with functions which preserve the majorization order. More specifically, the Schur-convex functions are real-valued functions $`f`$ such that $`xy`$ implies $`f(x)f(y)`$. Examples of Schur-convex functions include $`f(x)_ix_i\mathrm{log}(x_i)`$, $`f(x)_ix_i^k`$ (for any constant $`k1`$), $`f(x)_ix_i`$, and $`f(x)x_1^{}`$. More examples and a characterization of the Schur-convex functions may be found in . Each such Schur-convex function gives rise to an inequality relating the vector of probabilities $`(p_i)`$ in Equation (4) to the vector $`\lambda ^\rho `$. For example, we see from the Schur-convexity of $`_ix_i\mathrm{log}(x_i)`$ the useful inequality that $`H(p_i)S(\rho )`$, where $`H()`$ is the Shannon entropy, and $`S()`$ is the von Neumann entropy. (This result was obtained by Lanford and Robinson  using different techniques.) In general, any Schur-convex function will give rise to a similar inequality relating $`(p_i)`$ and $`\lambda ^\rho `$. A similar property related to convex functions has previously been noted (see the review  for an overview, as well as the original references ), however those results are a special case  of the more general result given here based upon Schur-convex functions. The earlier results may be obtained by noting that if $`f(x)`$ is convex then the map $`(p_i)_if(p_i)`$ is Schur-convex.

### C Representation of bipartite pure states

A third application of Theorem 3 gives us insight into the properties of pure states of bipartite systems. We state the result formally as follows:

Corollary 4: Suppose $`|\psi `$ is a pure state of a composite system $`AB`$ with Schmidt decomposition 

$`|\psi ={\displaystyle \underset{i}{}}\sqrt{p_i}|i_A|i_B.`$ (11)   
Then given a probability distribution $`(q_i)`$ there exists an orthonormal basis $`|i_A^{}`$ for system $`A`$ and corresponding pure states $`|\psi _i`$ of system $`B`$ such that

$`|\psi ={\displaystyle \underset{i}{}}\sqrt{q_i}|i_A^{}|\psi _i`$ (12)   
if and only if $`(q_i)(p_i)`$.

In the statement of Corollary 4 it is understood that if $`(q_i)`$ contains more terms than $`(p_i)`$ then the former vector should be extended by adding extra zeros. In the case where the number of terms in $`(q_i)`$ exceeds the number of dimensions of $`A`$’s Hilbert space, $`A`$’s Hilbert space must be extended so its dimension matches the number of terms in $`(q_i)`$.

Proof of Corollary 4:

To prove the forward implication, note that tracing out system $`A`$ in equations (11) and (12) gives $`_ip_i|i_Bi_B|=_iq_i|\psi _i\psi _i|`$, and thus by Theorem 3, $`(q_i)(p_i)`$. Conversely, suppose $`|\psi `$ has Schmidt decomposition given by (11), and that $`(q_i)(p_i)`$. Let $`\rho `$ be the reduced density matrix of system $`B`$ when $`A`$ is traced out,

$`\rho =\text{tr}_A(|\psi \psi |)={\displaystyle \underset{i}{}}p_i|i_Bi_B|.`$ (13)   
By Theorem 3, $`\rho =_iq_i|\psi _i\psi _i|`$ for some set of pure states $`|\psi _i`$. The state $`|\varphi `$ defined by

$`|\varphi {\displaystyle \underset{i}{}}\sqrt{q_i}|i_A|\psi _i`$ (14)   
is a purification of $`\rho `$, that is, a pure state of system $`AB`$ such that when system $`A`$ is traced out, $`\text{tr}_A(|\varphi \varphi |)=\rho `$. Thus $`|\psi `$ and $`|\varphi `$ are both purifications of $`\rho `$. It can easily be shown  that there exists a unitary matrix $`U`$ acting on system $`A`$ such that $`U|\varphi =|\psi `$. Defining $`|i_A^{}U|i_A`$ we see that

$`|\psi ={\displaystyle \underset{i}{}}\sqrt{q_i}|i_A^{}|\psi _i,`$ (15)   
as claimed.

QED

### D Communication cost of entanglement transformation

Corollary 4 can be used to give insight into a recent result in the study of entanglement transformation . Suppose Alice and Bob are in possession of an entangled pure state $`|\psi `$. They wish to transform this state into another pure state $`|\varphi `$, with the restriction that they may only use local operations on their respective systems, together with a possibly unlimited amount of classical communication. It was shown in  that the transformation can be made if and only if $`\lambda _\psi \lambda _\varphi `$, where $`\lambda _\psi `$ denotes the vector of eigenvalues of the reduced density matrix of Alice’s system when the joint Alice-Bob system is in the state $`|\psi `$, and $`\lambda _\varphi `$ is defined similarly for the state $`|\varphi `$.

To see how Corollary 4 applies in this context, suppose $`|\psi `$ and $`|\varphi `$ are bipartite states with Schmidt decompositions

$`|\psi `$ $`=`$ $`{\displaystyle \underset{i}{}}\sqrt{p_i}|i|i`$ (16)   
$`|\varphi `$ $`=`$ $`{\displaystyle \underset{i}{}}\sqrt{q_i}|i|i,`$ (17)   
where without loss of generality we may assume the two states have the same Schmidt bases, since local unitary transformations can be used to inter-convert between different Schmidt bases. Note that $`\lambda _\psi =(p_i)`$ and $`\lambda _\varphi =(q_i)`$. Suppose that $`\lambda _\psi =(p_i)\lambda _\varphi =(q_i)`$. By Corollary 4, and ignoring unimportant local unitary transformations, it is possible to write $`|\psi `$ and $`|\varphi `$ in the form

$`|\psi `$ $`=`$ $`{\displaystyle \underset{i}{}}\sqrt{p_i}|i|i`$ (18)   
$`|\varphi `$ $`=`$ $`{\displaystyle \underset{i}{}}\sqrt{p_i}|i|\psi _i,`$ (19)   
for some set of pure states $`|\psi _i`$. This form makes it quite plausible that the state $`|\psi `$ can be transformed into the state $`|\varphi `$ by local operations and classical communication: all that needs to be done is for Bob to transform $`|i`$ into $`|\psi _i`$ in such a way as to preserve coherence between different terms in the sum.

I have not found a general method utilizing this fact to transform $`|\psi `$ into $`|\varphi `$. However, it will now be shown how Corollary 4 can be applied successfully in the special case where $`|\psi `$ is a maximally entangled state of a $`d`$ dimensional system with a $`d^{}d`$ dimensional system,

$`|\psi ={\displaystyle \underset{i}{}}{\displaystyle \frac{|i|i}{\sqrt{d}}}.`$ (20)   
The new proof has the feature that it is exponentially more efficient from the point of view of classical communication than the protocol described in . The argument runs as follows. By Corollary 4 we can find pure states $`|\varphi _i`$ such that

$`|\varphi ={\displaystyle \underset{i}{}}{\displaystyle \frac{|i|\varphi _i}{\sqrt{d}}},`$ (21)   
up to local unitary transformations. Define an operator on Bob’s system,

$`F{\displaystyle \underset{i}{}}|\varphi _ii|,`$ (22)   
Ideally, we’d apply $`F`$ to the system $`B`$ taking $`|\psi `$ directly to $`|\varphi `$. This doesn’t work because $`F`$ isn’t unitary. Instead, we use $`F`$ to define a quantum measurement with essentially the same effect. Define

$`E{\displaystyle \frac{F}{\sqrt{\text{tr}(F^{}F)}}}.`$ (23)   
Let $`|0,\mathrm{},|d1`$ be the Schmidt basis for Bob’s system. Define operators $`X`$ and $`Z`$ by

$`X|j|j1;Z|j\omega ^j|j,`$ (24)   
where $``$ denotes addition modulo $`d`$, and $`\omega `$ is a $`d`$th root of unity. Define unitary operators $`U_{s,t}`$ by

$`U_{s,t}X^sZ^t.`$ (25)   
The indices $`s`$ and $`t`$ are integers in the range $`0`$ to $`d1`$. By checking on an operator basis and applying linearity it is easily verified that for any Hermitian $`A`$,

$`{\displaystyle \underset{st}{}}U_{s,t}^{}AU_{s,t}=\text{tr}(A)I.`$ (26)   
Therefore, defining $`E_{s,t}EU_{s,t}`$ gives

$`{\displaystyle \underset{st}{}}E_{s,t}^{}E_{s,t}=I.`$ (27)   
The set $`\{E_{s,t}\}`$ therefore defines a generalized measurement on Bob’s system with $`d^2`$ outcomes. Suppose Bob performs this measurement. If he obtains the result $`(s,t)`$ then the state of the system after the measurement is

$`{\displaystyle \underset{i}{}}{\displaystyle \frac{\omega ^{it}|i|\varphi _{is}}{\sqrt{d}}}.`$ (28)   
Bob sends the measurement result to Alice, which requires $`2\mathrm{log}_2d`$ bits of communication, and then Alice performs $`X^sZ^t`$ (where $`X`$ and $`Z`$ are now defined with respect to Alice’s Schmidt basis) on her system, giving the state

$`{\displaystyle \underset{i}{}}{\displaystyle \frac{|is|\varphi _{is}}{\sqrt{d}}},`$ (29)   
which is just $`|\varphi `$.

This protocol for entanglement transformation requires only $`2\mathrm{log}_2(d)`$ bits of communication, compared with the protocol in , which required $`d1`$. Another method  for achieving this result is as follows: Alice prepares locally a system $`A^{}B^{}`$ in a copy of $`|\varphi `$. She then uses the shared maximal entanglement $`|\psi `$ with Bob to teleport  system $`B^{}`$ to Bob, creating the desired state $`|\varphi `$. Again, this protocol requires $`2\mathrm{log}_2(d)`$ bits of communication.

The present approach is interesting, in that it does not require knowledge of the teleportation protocol in order to succeed. Moreover, the method used strongly suggests that it may be possible to always perform the transformation using $`O(\mathrm{log}_2d)`$ bits of communication, even when $`|\psi `$ is not maximally entangled, a result that does not appear obvious from the teleportation protocol. A method for doing so has recently been found using different methods, and will be reported elsewhere.

## IV Conclusion

The results reported here answer a fundamental question about the nature of the density matrix as a representation for ensembles of pure states, and give some elementary applications of this result to quantum mechanics and quantum information theory. I expect that the connection revealed here between majorization and ensembles of pure states will be of considerable use in future investigations of fundamental properties of quantum systems. 

## acknowledgments

Thanks to Sumit Daftuar and Andrew Landahl for pointing out some glitches in earlier versions of this work, and Armin Uhlmann for discussions on majorization. This work was supported by a Tolman Fellowship, and by DARPA through the Quantum Information and Computing Institute (QUIC) administered through the ARO.

## A Unitary-stochastic matrices and majorization

In this appendix we outline the constructive steps in the proof of Theorem 1. To begin, we first take a slight detour connecting majorization with a class of matrices known as T-transforms.

By definition, a T-transform is a matrix which acts as the identity on all but $`2`$ dimensions, where it has the form:

$`T=\left[\begin{array}{cc}t& 1t\\ 1t& t\end{array}\right],`$ (A3)   
for some parameter $`t`$, $`0t1`$. The following result connects majorization and T-transforms :

Theorem 5: If $`xy`$ there exists a finite set of T-transforms $`T_1,T_2,\mathrm{},T_n`$ such that $`x=T_1T_2\mathrm{}T_ny`$.

The converse of Theorem 5 is also true , but will not be needed. For convenience we provide details of the construction of the sequence $`T_1,\mathrm{},T_n`$ here.

Proof of Theorem 5:

The result is proved by induction on $`d`$, the dimension of the vector space $`x`$ and $`y`$ live in. For notational convenience we assume that the components of $`x`$ and $`y`$ have been ordered into decreasing order; if this is not the case then one can easily reduce to this case by insertion of appropriate transposition matrices (which are T-transforms). The result is clear when $`d=2`$, so let’s assume the result is true for arbitrary $`d`$, and try to prove it for $`d+1`$-dimensional $`x`$ and $`y`$.

Choose $`k`$ such that $`y_kx_1y_{k1}`$. Such a $`k`$ is guaranteed to exist because $`xy`$ implies that $`x_1y_1`$ and $`x_1x_{d+1}y_{d+1}`$. Choose $`t`$ such that

$`x_1=ty_1+(1t)y_k.`$ (A4)   
Now define $`z`$ to be the result of applying a T-transform $`T`$ with parameter $`t`$ to the $`1`$st and $`k`$th components of $`y`$, so that

$`z`$ $`=`$ $`Ty`$ (A5)   
$`=`$ $`(x_1,y^{}),`$ (A6)   
where

$`y^{}(y_2,\mathrm{},y_{k1},(1t)y_1+ty_k,y_{k+1},\mathrm{},y_{d+1}).`$ (A7)   
Define $`x^{}(x_2,x_3,\mathrm{},x_{d+1})`$. It is not difficult to verify that $`x^{}y^{}`$ (see  for details), and thus by the inductive hypothesis, $`x^{}=T_1\mathrm{}T_ry^{}`$ for some sequence of T-transforms in $`d`$ dimensions. But these T-transforms can equally well be regarded as T-transforms on $`d+1`$ dimensions by acting as the identity on the first dimension, and thus $`x=T_1\mathrm{}T_rTy`$, that is, $`x`$ can be obtained from $`y`$ by a finite sequence of T-transforms, as we set out to show.

QED

Note that the inductive step of the proof of Theorem 5 can immediately be converted into an iterative procedure for constructing the matrices $`T_1,\mathrm{},T_n`$, and also implies that $`n=d1`$ in a $`d`$-dimensional space. The proof of Theorem 1, which we now give, is also inductive in nature, and is easily converted into an iterative procedure for constructing an orthogonal matrix $`u=(u_{ij})`$ such that $`D`$ defined by $`D_{ij}u_{ij}^2`$ satisfies Theorem 1. Note again the convention that expressions like $`u_{ij}^2`$ represent the square of the real number $`u_{ij}`$, not the $`ij`$th component of the matrix $`u^2`$.

To prove Theorem 1 we use the decomposition $`x=T_1T_2\mathrm{}T_ny`$ from the proof of Theorem 5. The strategy is to use induction on $`n`$ to prove that $`T_1T_2\mathrm{}T_n=(W_{ij}^2)`$ for some orthogonal matrix $`W`$. Suppose $`n=1`$. Omitting components on which $`T_1`$ acts as the identity, we have

$`T_1=\left[\begin{array}{cc}t& 1t\\ 1t& t\end{array}\right]`$ (A10)   
for some $`t`$, $`0t1`$. Define a unitary matrix $`U`$ to act as the identity on all components on which $`T_1`$ acts as the identity, and as

$`U\left[\begin{array}{cc}\sqrt{t}& \sqrt{1t}\\ \sqrt{1t}& \sqrt{t}\end{array}\right],`$ (A13)   
on the components where $`T_1`$ acts non-trivially. It is clear that $`T_1=(U_{ij}^2)`$, as required.

To do the inductive step, suppose that products of $`n`$ T-transforms of the form used in the proof of Theorem 5 are ortho-stochastic, and consider the product $`T_1T_2\mathrm{}T_{n+1}`$. We assume $`T_{n+2k}`$ acts on components $`k`$ and component $`d_k>k`$, as per the proof of Theorem 5. Let $`P`$ be the permutation matrix which transposes components $`2`$ and $`d_1`$. (The following proof is more transparent if one assumes that $`d_1=2`$, and drops all reference to $`P`$, which is a technical device to make certain equations more compact.) Then

$`PT_{n+1}P=\left[\begin{array}{ccc}t& 1t& 0\\ 1t& t& 0\\ 0& 0& I_{d2}\end{array}\right],`$ (A17)   
where $`I_{d2}`$ is the $`d2`$ by $`d2`$ identity matrix. Furthermore, let us define a $`d1`$ by $`d1`$ matrix $`\mathrm{\Delta }`$ by

$`T_1T_2\mathrm{}T_n=\left[\begin{array}{cc}1& 0\\ 0& \mathrm{\Delta }\end{array}\right].`$ (A20)   
By the inductive hypothesis there is a $`d1`$ by $`d1`$ orthogonal matrix $`U_{ij}`$ such that $`\mathrm{\Delta }_{ij}=U_{ij}^2`$. Define a new matrix $`U^{}`$ by interchanging the role of the first and $`(d_11)`$th co-ordinates in $`U`$, $`U^{}=P^{}UP^{}`$, where $`P^{}`$ transposes the first and $`(d_11)`$th co-ordinates, and similarly define $`\mathrm{\Delta }^{}`$ by $`\mathrm{\Delta }^{}P^{}\mathrm{\Delta }P^{}`$. Then $`\mathrm{\Delta }_{ij}^{}=U_{ij}^2`$. Also we have

$`PT_1T_2\mathrm{}T_nP=\left[\begin{array}{cc}1& 0\\ 0& \mathrm{\Delta }^{}\end{array}\right].`$ (A23)   
Multiplying the previous equation by $`PT_{n+1}P`$ gives, from (A17) and the identity $`P^2=I`$,

$`PT_1T_2\mathrm{}T_{n+1}P=\left[\begin{array}{ccc}t& 1t& 0\\ (1t)\stackrel{}{\delta }& t\stackrel{}{\delta }& \stackrel{~}{\mathrm{\Delta }},\end{array}\right],`$ (A26)   
where $`\stackrel{}{\delta }`$ is the first column of $`\mathrm{\Delta }^{}`$, and $`\stackrel{~}{\mathrm{\Delta }}`$ is the $`d2`$ by $`d1`$ matrix that results when the first column of $`\mathrm{\Delta }^{}`$ is removed. Let $`\stackrel{~}{U}`$ denote the $`d2`$ by $`d1`$ matrix that results when the first column of $`U^{}`$ is removed, and let $`\stackrel{}{u}`$ denote the first column of $`U^{}`$. Define a $`d`$ by $`d`$ matrix $`V`$ by

$`V\left[\begin{array}{ccc}\sqrt{t}& \sqrt{1t}& 0\\ \sqrt{1t}\stackrel{}{u}& \sqrt{t}\stackrel{}{u}& \stackrel{~}{U}\end{array}\right].`$ (A29)   
We claim that $`V`$ is an orthogonal matrix. To see this we need to show that the columns of $`V`$ are of unit length and orthogonal. The length of the first column is

$`\sqrt{t+(1t)\stackrel{}{u}\stackrel{}{u}}=\sqrt{1}=1.`$ (A30)   
A similar calculation shows that the second column is of unit length. The remaining columns are all of unit length since they are all columns of the unitary matrix $`U^{}`$. Simple algebra along similar lines can be used to check that the correct orthogonality relations between columns of $`V`$ are satisfied. Observe that $`PT_1T_2\mathrm{}T_{n+1}P=(V_{ij}^2)`$, so if we define $`WPVP`$, we see that $`W`$ is an orthogonal matrix such that $`T_1T_2\mathrm{}T_{n+1}=(W_{ij}^2)`$, which completes the induction.