5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @ChrisRamsey But I think the equation in the question describes an isometry. I think the right equation is $(AA^t)^2=AA^t$, right? $\endgroup$
    – vidyarthi
    Jul 30, 2020 at 20:40
  • 1
    $\begingroup$ @vidyarthi Any doubly stochastic idempotent will be a partial isometry. The OP gives a description of the idempotents and most are not permutations. $\endgroup$ Jul 30, 2020 at 20:45
  • $\begingroup$ @ChrisRamsey see my answer now. $\endgroup$
    – vidyarthi
    Jul 30, 2020 at 21:09
  • $\begingroup$ @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$. $\endgroup$
    – Ruy
    Jul 30, 2020 at 21:11

2 Answers 2

0
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ In the last statement, I think you concluded that each block of $A$ is $P(n)$ instead of $A=P(n)$, right? $\endgroup$
    – vidyarthi
    Jul 31, 2020 at 13:04
  • $\begingroup$ by the way, I have modified my answer similarly. See if it helps $\endgroup$
    – vidyarthi
    Jul 31, 2020 at 13:26
  • $\begingroup$ “... you concluded that each block of 𝐴 is 𝑃(𝑛) instead of 𝐴=𝑃(𝑛), right?” Yep! This is what I meant by “Dealing with each block separately...” $\endgroup$
    – Ruy
    Jul 31, 2020 at 17:27
  • $\begingroup$ 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 $\endgroup$
    – vidyarthi
    Aug 5, 2020 at 12:13
  • $\begingroup$ @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. $\endgroup$
    – Ruy
    Aug 10, 2020 at 13:52
-1
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ I do not see why $U$, $D$, and $E$ must be doubly stochastic. But the guess is certainly very interesting! $\endgroup$
    – Ruy
    Jul 30, 2020 at 21:14
  • $\begingroup$ @Ruy yes, they need not be. Added the scaling factors $\endgroup$
    – vidyarthi
    Jul 30, 2020 at 21:33
  • $\begingroup$ Now I should say that I do not see why 𝑈, 𝐷, and 𝐸 must be scalar multiples of doubly stochastic matrices. $\endgroup$
    – Ruy
    Jul 31, 2020 at 1:03
  • $\begingroup$ I think I can prove that your conclusion is corrrect, but the proof is a bit envolving. Will try to write it down soon. $\endgroup$
    – Ruy
    Jul 31, 2020 at 1:22
  • $\begingroup$ 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. $\endgroup$
    – Ruy
    Jul 31, 2020 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.