# Doubly-stochastic partial-isometric matrices

An $$n\times n$$ matrix $$A$$ with nonegative real entries $$a_{ij}$$ is said to be doubly stochastic if $$\sum_{i=1}^na_{ij} = 1$$, for all $$j$$, and $$\sum_{j=1}^na_{ij}=1$$, for all $$i$$.

Much is known [1] about the algebraic structure of the semigroup $$\Omega _n$$ formed by all doubly stochastic $$n\times n$$ matrices. For example, permutation matrices are the only invertible doubly stochastic matrices whose inverse is also doubly stochastic. On the other hand [3], the idempotent elements in $$\Omega _n$$ are precisely the direct sums of $$k\times k$$ matrices of the form $$\pmatrix{ 1/k & 1/k & \ldots & 1/k \cr \vdots & \vdots & \ddots & \vdots\cr 1/k & 1/k & \ldots & 1/k \cr}$$ together with their conjugates by permutation matrices.

Question: Which doubly stochastic matrices are partial isometries (i.e. satisfy the equation $$AA^tA = A$$)?

See [2] for the characterization of normal, partial isometric, doubly stochastic matrices.

[1] Farahat, H. K., The semigroup of doubly-stochastic matrices, Proc. Glasg. Math. Assoc. 7, 178-183 (1966). ZBL0156.26001.

[2] Prasada Rao, P. S. S. N. V., On generalized inverses of doubly stochastic matrices, Sankhyā, Ser. A 35, 103-105 (1973). ZBL0301.15005.

[3] Sinkhorn, R., Two results concerning doubly stochastic matrices, Am. Math. Mon. 75, 632-634 (1968). ZBL0162.04205.

• @ChrisRamsey But I think the equation in the question describes an isometry. I think the right equation is $(AA^t)^2=AA^t$, right? Jul 30, 2020 at 20:40
• @vidyarthi Any doubly stochastic idempotent will be a partial isometry. The OP gives a description of the idempotents and most are not permutations. Jul 30, 2020 at 20:45
• @ChrisRamsey see my answer now. Jul 30, 2020 at 21:09
• @vidyarthi, here are two results from Halmos' "A Hilbert Space Problem Book", which say that the two characterizations are equivalent: (Problem 127) A bounded linear transformation $U$ is a partial isometry if and only if $U^*U$ is a projection, and (Corollary 3) A bounded linear transformation $U$ is a partial isometry if and only if $U = UU^*U$.
– Ruy
Jul 30, 2020 at 21:11

The following is an attempt to validate the conclusion proposed by @vidyarthi.

Theorem: Every doubly-stochastic partial-isometric matrix is the product of a permutation matrix and a doubly-stochastic projection.

Proof: Given a doubly-stochastic partial-isometric matrix $$A$$, one has that $$A^tA$$ and $$AA^t$$ are doubly-stochastic projections, so by Theorem 2 in (Sinkhorn, R., Two results concerning doubly stochastic matrices, Am. Math. Mon. 75, 632-634 (1968). ZBL0162.04205) there are permutation matrices $$U$$ and $$V$$ such that $$U^tA^tAU = P(k_1)\oplus P(k_2)\oplus \cdots \oplus P(k_n)$$ and $$V^tAA^tV = P(l_1)\oplus P(l_2)\oplus \cdots \oplus P(l_m),$$ where, for any integer $$k$$, $$P(k):= \pmatrix{ 1/k & 1/k & \ldots & 1/k \cr \vdots & \vdots & \ddots & \vdots\cr 1/k & 1/k & \ldots & 1/k \cr}.$$ Replacing $$A$$ with $$V^tAU$$, we may assume that $$U$$ and $$V$$ coincide with the identity matrix and hence $$U$$ and $$V$$ will henceforth be ommitted.

Set $$c(k)=(1/\sqrt k,1/\sqrt k,…,1/\sqrt k) ∈ \mathbb R^k$$, so that $$c(k)$$ is a unit vector spanning the range of $$P(k)$$. Moreover the range of the projection $$A^tA$$ above admits an orthonormal basis formed by the vectors $$u_1 = c(k_1)\oplus 0_{k_2}\oplus \cdots \oplus 0_{k_n},$$ $$u_2 = 0_{k_1}\oplus c(k_2)\oplus \cdots \oplus 0_{k_n},$$ $$...$$ $$u_n = 0_{k_1}\oplus 0_{k_2}\oplus \cdots \oplus c(k_n),$$ a similar reasoning yielding a basis $$\{v_1, v_2, …, v_m\}$$ for the range of $$AA^t$$. The initial and final projections of a partial isometry share rank, so $$n=m$$, and we claim that, up to a permutation of indices $$i$$, one has that $$k_i=l_i$$, for all $$i$$.

Notice that $$A$$ maps $$\hbox{span}\{u_i\}$$ isometrically onto $$\hbox{span}\{v_i\}$$ so, for $$i\neq j$$, one has that $$Au_i$$ and $$Au_j$$ are orthogonal vectors. However these vectors have nonnegative coordinates so their support (set of indices for nonzero coordinates) must be disjoint. By the pigeonhole principle each $$u_i$$ must therefore be mapped under $$A$$ to a scalar multiple of some $$v_j$$. By positivity and norm preservation these scalars must coincide with 1 so there is a permutation $$\sigma$$ such that $$Au_i=v_{\sigma (i)}$$, for all $$i$$.

Observe that, being doubly-stochastic, $$A$$ leaves invariant the linear functional $$\Sigma$$ which sums all of the coordinates of a vector. Noticing that $$\Sigma(u_i)=\sqrt{k_i}$$, while $$\Sigma(v_j)=\sqrt{l_j}$$, we deduce that $$k_i=l_{\sigma (i)}$$.

It is now easy to see that there exists a permutation matrix $$W$$ such that $$Wu_i = v_{\sigma (i)}$$. Letting $$B=W^tA,$$ we then have that $$Bu_i=u_i$$, while $$B^tB=A^tA$$.

It follows that $$B$$ is a partial isometry coinciding with the identity operator on its initial space, and hence that $$B$$ coincides with its initial projection $$B^tB$$. This leads to $$A=WB=WB^tB=WA^tA.$$

• In the last statement, I think you concluded that each block of $A$ is $P(n)$ instead of $A=P(n)$, right? Jul 31, 2020 at 13:04
• by the way, I have modified my answer similarly. See if it helps Jul 31, 2020 at 13:26
• “... you concluded that each block of 𝐴 is 𝑃(𝑛) instead of 𝐴=𝑃(𝑛), right?” Yep! This is what I meant by “Dealing with each block separately...”
– Ruy
Jul 31, 2020 at 17:27
• Here is the desired counterexample: we have the product of $\frac1{3}\begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}$ and $\frac1{3}\begin{pmatrix}-1&2&2\\2&-1&2\\2&2&-1\end{pmatrix}$ to be a stochastic partial isometric matrix $\frac1{3}\begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}$. Hence, your argument (as well as mine before) fails. Modified my answer Aug 5, 2020 at 12:13
• @vidyarthi, If I understand it right you are claiming that the third matrix in your message is a counter-example. If so I don't think I agree because this matrix is itself a doubly stochastic projection.
– Ruy
Aug 10, 2020 at 13:52

From here, we have that a square matrix is a partial isometry if and only if it is of the form $$A=UD=EU$$, where $$D, E$$ are idempotent and $$U$$ is unitary. Translating this to our case, we have that a doubly stochatic matrix is a partial isometry when it is a product of an orthogonal matrix (scaled by a scalar) with an idempotent matrix (again scaled by appropriate scalar) both of whose row and column sums equals $$1$$. The rank of the matrix equals that of the unscaled idempotent matrix.

To further elaborate as to why the unscaled matrices $$E,D,U$$ have the said property, suppose $$A=EU$$, where $$E$$ is idempotent and $$U$$ be unitary (orthogonal), we obtain, for the eigenvector $$v=(1\ 1\ 1\ldots\ 1)^t$$ of $$A$$, we get that $$Av=v\implies EUv=v=E^2Uv=E(EUv)=Ev$$, thereby showing that $$v$$ is an eigenvector of $$E$$ with eigenvalue $$1$$, thereby clearly implying $$E$$ has row sum of each row equal to $$1$$. A similar reasoning with the transpose of $$A$$ shows that $$E$$ should also have each column sum equal to $$1$$, since $$E^t$$ is also idempotent. Now, using that $$A=UD$$, and the vector $$v^t$$ as a left eigenvector , we obtain that both $$D$$ and $$U$$ also have both row and column sum equal to $$1$$.

• I do not see why $U$, $D$, and $E$ must be doubly stochastic. But the guess is certainly very interesting!
– Ruy
Jul 30, 2020 at 21:14
• @Ruy yes, they need not be. Added the scaling factors Jul 30, 2020 at 21:33
• Now I should say that I do not see why 𝑈, 𝐷, and 𝐸 must be scalar multiples of doubly stochastic matrices.
– Ruy
Jul 31, 2020 at 1:03
• I think I can prove that your conclusion is corrrect, but the proof is a bit envolving. Will try to write it down soon.
– Ruy
Jul 31, 2020 at 1:22
• I think this is not yet correct. The matrix $E={1\over30}\pmatrix{ 25& -5& 10 \cr -5& 25& 10 \cr 10& 10& 10}$ is idempotent and has $(1,1,1)$ as a fixed point and yet it is not doubly-stochastic.
– Ruy
Jul 31, 2020 at 17:23