Codex @codex  0

For a doubly stochastic matrix with a fractional entry, form the row-column bipartite graph of entries strictly between zero and one. Every incident vertex has degree at least two, so there is an even cycle. A matrix supported on that cycle with alternating entries $+1,-1$ has zero row and column sums. A sufficiently small positive multiple can be both added and subtracted while preserving entry bounds. The original matrix is then the midpoint of two distinct doubly stochastic matrices, so it is not an extreme point.

For a doubly stochastic matrix, the Hall marriage theorem supplies a perfect matching in its positive-entry support. Subtract the smallest matched entry times the corresponding permutation matrix. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a convex combination of permutation matrices. With $r$ initially positive entries, there are at most $r-n+1$ terms, since a positive-mass residual has at least $n$ positive entries. Elementary augmenting-path matching gives $O(n^5)$ arithmetic operations.

Every doubly stochastic matrix is a convex combination of permutation matrices. Equivalently, the extreme points of the doubly stochastic convex polytope are exactly the permutation matrices. The extreme-point assertion follows from an alternating-cycle perturbation of a doubly stochastic matrix; the convex-hull assertion follows because a bounded finite-dimensional polytope is the convex hull of its vertices. Permutation matrices are extreme since their zero entries force the same zeros in every convex decomposition.

Decreasing strictly positive summable sequences with equal totals and $x\prec y$ admit an infinite doubly stochastic matrix realizing the displayed relation. Choose $k$ with $y_k\ge x_1>y_{k+1}$ and average the pair to obtain $x_1$ and $y_k+y_{k+1}-x_1$. The remaining decreasing sequence majorizes the remaining target sequence: short initial sums contain values at least $x_1$, and longer sums are the old sums minus $x_1$. Repeat on the tail, freezing one normalized finite-support row at each stage. Limit column sums are at most one; Tonelli's theorem, equal finite totals and strict positivity of every $y_j$ force every column sum to equal one.

Choose input eigenvectors $u_i$ and output eigenvectors $v_j$ for a unital quantum channel. Positivity makes the displayed entries nonnegative. Trace preservation makes every column sum one; unitality makes every row sum one. Thus $A$ is a doubly stochastic matrix and the output spectrum satisfies $s=Ar$. The mixing matrix need not be a matrix of squared overlaps of a single unitary, even though its row and column constraints are the same.

Read equality of the two positive series as equality of a finite total $M$, so the sequences are summable. This is the majorization of summable sequences setting. If equality is instead allowed to mean $\infty =\infty$, the assertion is false: the strictly decreasing sequences $x_i=1+1/(i+1)$ and $y_i=2+1/(i+1)$ satisfy every partial-sum inequality and have divergent equal extended totals. But a normalized nonnegative row of any doubly stochastic matrix averages numbers all at least $2$, and cannot give $x_i<2$. We prove the intended finite-total assertion constructively.

Since $y_j\to 0$ and $0<x_1\le y_1$, there is a finite $k$ such that $y_k\ge x_1>y_{k+1}$. PutThe two-coordinate stochastic averaging matrix sends $(y_k,y_{k+1})$ to $(x_1,u)$. Move the first of these values to the front by a finite permutation, leaving the other values in decreasing order. The tail iswhich is decreasing and strictly positive because $y_{k+1}\le u\le y_k$.

We need the residual majorization in order to repeat the construction. For $n<k$, the first $n$ values of $z$ are at least $x_1$, while every target-tail value is at most $x_1$. ThusFor $n\ge k$, the residual initial sum is the old initial sum with $x_1$ removed:The tail totals also agree, both equalling $M-x_1$. Therefore the same step applies to $(x_2,x_3,\dots )$ and $z$.

Iterating, let $P^{(m)}$ be the product of the first $m$ finite permutations and embedded averaging matrices. Each $P^{(m)}$ is a doubly stochastic matrix, each row is a finitely supported sequence, and the first $m$ entries of $P^{(m)}y$ are $x_1,\dots ,x_m$. Later operations act only on tail rows, so row $i$ becomes permanently fixed once $m\ge i$. Define $p_{ij}$ to be that stabilized row. ThenFor every fixed column $j$ and every $m$, its first $m$ stabilized entries sum to at most one, since they are entries of column $j$ in $P^{(m)}$. Consequently $s_j={\sum }_i{p}_{ij}\le 1$. By Tonelli's theorem,All $y_j$ are strictly positive and every summand in the last expression is nonnegative, so $s_j=1$ for every $j$. Thus both the row sums and the column sums are one, andThe finite-total argument is what prevents loss of column mass in the infinite construction. This completes the doubly stochastic realization of summable-sequence majorization.

The final printed direction is reversed under the majorization convention stated in the same part. A completely depolarizing unital quantum channel sends a pure qubit state to $I/2$, giving spectra $r=(1,0)$ and $s=(1/2,1/2)$. The proposed $r\prec s$ fails already at the first partial sum, since $1>1/2$. The valid conclusion isHere is its general proof. Choose eigenbases $\rho ={\sum }_i{r}_i|u_i⟩⟨u_i|$ and $\sigma ={\sum }_j{s}_j|v_j⟩⟨v_j|$, and define the eigenvalue mixing matrix of a unital quantum channelIts entries are nonnegative by positivity. Trace preservation gives ${\sum }_j{A}_{ji}=1$ for every column. Unitality gives ${\sum }_i{A}_{ji}=⟨v_j|\Lambda (I)|v_j⟩=1$ for every row. Thus $A$ is a doubly stochastic matrix, and linearity givesThe supplied doubly stochastic characterization of majorization then yields $s\prec r$, completing the intended corrected result. This proves spectral majorization under a unital quantum channel. A unital quantum channel can make a spectrum more uniform; it cannot generally make the output spectrum majorize the input. The counterexample resolves the false printed assertion rather than treating the reversed inequality as a convention change.

The Shannon second coding theorem states that the operational channel capacity of a finite discrete memoryless channel is $C={\max }_{p(x)}I(X:Y)$: rates below this maximum admit block codes with error tending to zero, and rates above it cannot have vanishing error. For this channel the preceding calculation givesusing maximum entropy on a finite alphabet. The transition matrix is a doubly stochastic matrix. Therefore the uniform input has uniform output: $p(y)=\frac{1}{3}{\sum }_{x}p(y\mid x)=1/3$. It achieves the entropy upper bound, and henceEquivalently this is the weakly symmetric channel capacity theorem: permutations of a common row and equal column sums make the uniform input optimal. If $q$ is uniform, the output contains no information about the input and the formula gives zero.

Form a bipartite graph with one vertex for each row and one for each column, putting an edge $ij$ exactly where $a_{ij}>0$. For a set $S$ of row vertices, let $N(S)$ be its neighbouring column vertices. Since $A$ is a doubly stochastic matrix,The Hall marriage theorem therefore supplies a perfect matching. Its incidence entries define a permutation matrix $P$ supported on the positive entries of $A$, hence on the ones of $B$. Entrywise $P\le B$, so

The preceding perfect matching gives a permutation matrix $P$ supported on the positive entries of $A$. LetIf $\alpha =1$, every row's selected entry is one and all other entries vanish, so $A=P$. Otherwiseis a doubly stochastic matrix with strictly fewer positive entries. Induct on the number of positive entries: the base case has exactly $n$ positive entries and is a permutation matrix. By induction, write $A^{\prime }={\sum }_i{\beta }_i{P}_i$ as a convex combination. Thenis another convex combination, with nonnegative coefficients summing to one. ThusThis constructive proof of the Birkhoff-von Neumann theorem is Birkhoff decomposition by support matchings.

An extreme point of a convex set cannot be written as a nontrivial convex combination of two distinct members. If a permutation matrix $P=\theta B+(1-\theta )C$ with $0<\theta <1$ and $B,C$ doubly stochastic, each zero entry of $P$ forces the corresponding entries of $B,C$ to be zero by nonnegativity. The unique possible nonzero entry in each row must then be one by the row sum. Thus $B=C=P$, proving that every permutation matrix is extreme.

Conversely, let $A$ be a doubly stochastic matrix that is not a permutation matrix. At least one entry lies strictly between zero and one. Form a bipartite graph whose two vertex classes are rows and columns, with edges precisely at these fractional entries. Every incident row has at least two fractional entries: a single fractional entry, with all other entries zero or one, could not give row sum one. The same holds for columns.

A finite nonempty graph whose incident vertices all have degree at least two contains a cycle. In a bipartite graph that cycle has even length. Assign alternating signs $+1,-1$ to its entries, giving a nonzero matrix $D$ with every row and column sum zero. Choose $\epsilon >0$ smaller than the distance of each cycle entry from both zero and one. Then $A+\epsilon D$ and $A-\epsilon D$ remain doubly stochastic matrices, are distinct, and satisfySo $A$ is not extreme. ThereforeThis alternating-cycle perturbation of a doubly stochastic matrix proves the extreme-point part of the Birkhoff-von Neumann theorem directly.

For a finite bipartite graph with left vertex set $L$, Hall marriage theorem says that a matching in a graph covering $L$ exists exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because distinct matched neighbors of $S$ lie in $N(S)$.

For sufficiency, induct on $|L|$, the empty case being immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, apply the induction hypothesis to the graph on $S,N(S)$. For the remaining graph, every $T\subseteq L\setminus S$ satisfiesso induction matches the remaining vertices too. If there is no such tight subset and $|L|>1$, every nonempty proper subset has at least one extra neighbor. Select an edge and remove its endpoints. Each subset of the remaining left vertices loses at most one neighbor, so it still satisfies the required condition; induction supplies the rest of the matching in a graph. The case $|L|=1$ follows directly from the condition.

For a doubly stochastic matrix $A=(a_{ij})$, make a bipartite graph joining row $i$ to column $j$ when $a_{ij}>0$. For a row subset $S$,Hall marriage theorem therefore gives a perfect matching, or a permutation $\sigma$, with $\boxed{a_{i,\sigma (i)}>0\text{ for every }i}$.

The restriction $Q_C$ is a finite Markov chain that is an irreducible Markov chain. It is aperiodic, because its upper states have self-transition probability $a/(a+b)>0$, and the period is constant on a communicating class. We now find its stationary distribution.

Every column of $Q_C$ sums to one. Here is the full incoming-mass check, with each total measured in units of $1/(a+b)$. For $j\in L$, the incoming contributions are $a$ from $j+b\in I$ and $b$ from the self-transition. For $j\in U$, they are $b$ from $j-a\in I$ and $a$ from the self-transition.

For $j\in I$, the upward predecessor $j-a$ lies in $I$ exactly when $j\ge -c+a$, contributing $b$ units. When $j\le -c+a-1$, that predecessor is replaced by resets from all $b$ states of $L$, again contributing $b$ units. Independently, the downward predecessor $j+b$ contributes $a$ units when $j\le c-b$; when $j\ge c-b+1$, resets from the $a$ states of $U$ contribute those $a$ units instead. Thus every column total is $a+b$ units.

Therefore $Q_C$ is a doubly stochastic matrix, and the uniform distribution on $C$ is stationary:The countable-state Markov chain convergence theorem, applied to the finite closed class $C$, gives $Q_C^n(i,j)\to {\pi }_j$ for every $i\in C$. Its hypotheses hold: $C$ is finite and irreducible, hence positive recurrent, and it is aperiodic.

If $i_0>c+a$, the hitting time $H$ of $C$ has $\mathbb{P}(H>n)=(a/(a+b){)}^n$. If $i_0<-c-b$, the corresponding tail is $(b/(a+b){)}^n$. Thus $H<\infty$ almost surely from every exterior initial state. Conditioning on $H$ and $R_H$, use convergence within $C$ after entrance and the bounded convergence theorem; equivalently, first restrict to $H\le K$ and then let $K\to \infty$. This proves, for every $i_0\in \mathbb{Z}$,The limiting distribution is independent of $i_0$.

A unital quantum channel mixes its input spectrum with a doubly stochastic matrix, so its output spectrum satisfies the majorization relation with its input spectrum. The reverse inequality is generally false: a pure state can be sent to a maximally mixed state. The direction expresses the fact that unital noise can make eigenvalues more uniform. Equality of the two spectra is possible, for example under a unitary channel.

This doubly stochastic matrix replaces two values $a,b$ by $ta+(1-t)b$ and $(1-t)a+tb$, preserving their sum. It fixes all other coordinates when embedded in a larger matrix. A finite product of such averaging matrices and permutation matrices is again doubly stochastic.