Frobenius normal form of a doubly stochastic matrix

Question

If $A \in M_n(\mathbb{C})$, then $A$ is called reducible if there is a permuation matrix $P$ such that $$ P^\top A P = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}, $$ in which $A_{11}$ and $A_{22}$ are square matrices of order at least one. If $A$ is not reducible, then $A$ is called irreducible. Notice that, with this definition, every one-by-one matrix is irreducible. A matrix $A$ is irreducible if and only if its directed graph or digraph is strongly connected.

It is known (see, e.g., Brualdi and Ryser [Theorem 3.2.4; MR1130611]) that if $A \in M_n(\mathbb{C})$, then $A$ is irreducible or there is a permutation matrix $P$ such that \begin{equation} P^\top A P = \begin{bmatrix} A_{11} & \cdots & A_{1k} \\ & \ddots & \vdots \\ & & A_{kk} \end{bmatrix}, \tag{1} \label{fnf} \end{equation} in which the matrices $A_{11},\dots, A_{kk}$ are square, irreducible matrices. The matrix in \eqref{fnf} is called a Frobenius or irreducible normal form (of $A$) (FNF) and it is not unique. However, the blocks $A_{11},\dots, A_{kk}$ are unique up to permutation similarity.

A matrix $A$ is nonnegative ($A \ge 0$) if $a_{ij} \ge 0$, $1 \le i,j \le n$. A nonnegative matrix is stochastic if $Ae = e$ and doubly stochastic if, in addition, $A^\top e = e$ (i.e., $A$ has row and column sums equal to one).

In a 1965 paper, Perfect and Mirsky [MR0175917] state, without proof, that if $A$ is a doubly stochastic matrix, then every FNF of $A$ is of the form $$ \begin{bmatrix} A_{11} & & \\ & \ddots & \\ & & A_{kk} \end{bmatrix}, $$ i.e., every doubly stochastic matrix is either irreducible or is permutationally similar to a direct sum of irreducible, doubly stochastic matrices. After giving the result Perfect and Mirsky state:

"This result is almost certainly well-known. As, furthermore, it follows very easily from the definitions, we omit the details of the proof." – p. 38.

This result is easy to establish for matrices of order less than or equal to four, but does not seem obvious or seem to follow simply from the definitions above.

Question 1: Is this result obvious or is there a simple proof of this fact?

Question 2: Does anybody know of a reference?

Answer 1

The matrix $P^\top AP$ is doubly stochastic. Suppose that $A_{11}$ is $m_{1} \times m_{1}.$ Note that the sum of the entries of each column of $A_{11}$ is $1$,and the sum of entries in each row of $A_{11}$ is at most $1$ (using non-negativity of all entries of $P^\top AP)$. Notice that the sum of all entries of $A_{11}$ is $m_{1}$. Hence, the sum of the entries of each row of $A_{11}$ is in fact $1$ (if any of the row sums were strictly less than $1$, then the sum of the row-sums, which equals the sum of the entries of $A_{11}$, would be strictly less than $m_1$, a contradiction), i.e., $A_{11}$ is doubly stochastic. Thus, $A_{12},A_{13},\ldots,A_{1k}$ are all zero. Likewise, $A_{22}$ must be doubly stochastic and $A_{23}, \ldots , A_{2k}$ must all be zero, and so on.

Answer 2

Here is a proof of the fact claimed by Perfect and Mirsky.

Proof. Let $A$ be doubly stochastic and let $B = P^TAP$ be a Frobenius normal form of $A$, which is given as in the question. Then $B$ is doubly stochastic, too. Fix $j \in \{2, \dots, k\}$. We show that all entries of $B$ that are located above the block $A_{jj}$ are $0$.

Let $i, i+1,\dots,i+m-1$ denote those $m$ subsequent indices in $\{1,\dots,n\}$ where the block matrix $A_{jj}$ is located in $B$.

We need the following four objects:

• $I = \{x \in \mathbb{C}^n: \, x_\ell = 0 \text{ for } \ell \ge i \}$.

• $J = \{x \in \mathbb{C}^n: \, x_\ell = 0 \text{ for } \ell < i \}$.

• $e_I = (1,\dots,1,0,\dots,0)$, where the ones are located exactly at the positions $1,\dots,i-1$ (i.e. $e_I \in I$ and $I$ is the so-called ideal generated by $e_I$ in the lattice sense).

• $e_J = (0,\dots,0,1,\dots,1)$, where the ones are located exactly at the positions $i,\dots,n$ (i.e. $e_J \in J$ and $J$ is the ideal generated by $e_J$).

Now we make a couple of observations:

(a) $I$ is invariant under $B$, as follows from the special form of $B$. This implies that $Be_I \in I$. On the other hand we have $Be_I \le Be = e$, so we conclude that actually $Be_I \le e_I$.

(b) Now we observe that $e^T Be_I = e^T e_I$, which implies that no component of $Be_I$ can by strictly smaller than the corresponding component of $e_I$; so we actually have $Be_I = e_I$.

(c) Since $Be = e$, the equality $Be_I = e_I$ readily implies that we also have $Be_J = e_J$. Consequently, $B$ also leaves $J$ invariant. This in turn implies that all entries of $B$ above of the block $A_{jj}$ are $0$.

Remark. I think what makes the above proof maybe a bit counterintuitive is the handling of all the indices. The essence of the proof (and, one might argue, also of the result quoted from Perfect and Mirsky) is that if, under the given assumptions, $A$ leaves an ideal $I$ invariant, then it also leaves the orthogonal ideal of $I$ invariant (where "orthogonal" in meant the lattice sense). By the way, this abstract version of the result generalizes very nicely to the infinite dimensional setting.