Doubly-stochastic partial-isometric matrices

Question

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.

Answer 1

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. $$

Answer 2

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$.