The Subtraction Step in Matrix Decomposition

The Residual-Matrix Invariant

A doubly stochastic matrix has nonnegative entries, and every row and column sums to $1$. The Birkhoff–von Neumann theorem expresses such a matrix as a weighted sum of permutation matrices. The key operation behind that decomposition is a subtraction: choose positive entries forming a permutation diagonal, subtract the smallest of them from each selected position, and leave every other entry unchanged.

The choice of the smallest selected entry matters. It ensures that no entry becomes negative, while at least one selected positive entry becomes zero. At the same time, every row and every column loses the same amount. These facts give a precise invariant for the matrix remaining after each subtraction.

Definition: A nonnegative $n\times n$ matrix $R=(r_{ij})$ is row-and-column regular with sum $r$ if every row sum and every column sum equals the same number $r\geq 0$. Its support is the set of positions $(i,j)$ for which $r_{ij}>0$. A positive permutation diagonal is a selection of positions $(i,\pi(i))$, one in each row and one in each column, such that $r_{i,\pi(i)}>0$ for every $i$, where $\pi$ is a permutation of $\{1,\dots,n\}$.

The permutation matrix $P_\pi$ for $\pi$ has entry $1$ at each position $(i,\pi(i))$ and entry $0$ elsewhere. Thus a positive permutation diagonal of $R$ is exactly a permutation matrix whose $1$-entries all lie in the support of $R$. A doubly stochastic matrix is row-and-column regular with sum $1$.

Why a Nonzero Residual Has a Positive Permutation Diagonal

To apply the subtraction, we need a positive permutation diagonal in the current residual matrix, not just in the original matrix. The equal-sum invariant guarantees one whenever the common sum is positive.

Lemma: Let $R$ be a nonnegative $n\times n$ matrix whose row and column sums all equal $r>0$. Then $R$ has a positive permutation diagonal.

Proof. Form a bipartite graph with one vertex for each row and one vertex for each column; join row $i$ to column $j$ exactly when $r_{ij}>0$. For a set $S$ of row vertices, let $N(S)$ be the set of column vertices adjacent to at least one row in $S$. The entries in the rows indexed by $S$ sum to $r|S|$. Every positive entry in those rows lies in a column of $N(S)$. Since all entries are nonnegative, their total is at most the sum of all entries in the columns indexed by $N(S)$, which is $r|N(S)|$. Therefore $r|S|\leq r|N(S)|$, and, since $r>0$, $|S|\leq |N(S)|$ for every set $S$ of rows. Hall’s condition holds, so Hall’s theorem gives a matching covering every row. There are $n$ rows and $n$ columns, so this matching also uses every column. Its selected positions form a positive permutation diagonal. $\square$

If the common sum is $0$, no such selection is needed: nonnegativity and a zero row sum force every entry in that row to be zero. Applying this to every row shows that $R$ is the zero matrix. Thus the two cases are exact: a positive common sum gives a positive permutation diagonal, while a zero common sum means the residual is finished.

The Subtraction Step

Theorem: Let $R=(r_{ij})$ be a nonnegative $n\times n$ matrix whose row and column sums all equal $r>0$. Choose a positive permutation diagonal $(i,\pi(i))$, and set $$ \alpha=\min_{1\leq i\leq n} r_{i,\pi(i)}. $$ Then $R'=R-\alpha P_\pi$ is nonnegative, every row and column sum of $R'$ is $r-\alpha$, and the support of $R'$ is a proper subset of the support of $R$.

Proof. The selected entries $r_{i,\pi(i)}$ are positive, so their minimum $\alpha$ is positive. For a selected position, $r_{i,\pi(i)}\geq\alpha$, and subtraction leaves $r_{i,\pi(i)}-\alpha\geq0$. Every unselected entry is unchanged and nonnegative. Thus $R'$ is nonnegative.

Each row has exactly one selected position, so its sum decreases by exactly $\alpha$, from $r$ to $r-\alpha$. Each column also has exactly one selected position, so each column sum decreases by exactly $\alpha$. In particular, $r-\alpha\geq0$, since it is a row sum of the nonnegative matrix $R'$.

At least one selected entry attains the minimum $\alpha$, and that entry becomes $0$. No entry outside the selected positions changes, and no zero entry becomes positive. Hence the support of $R'$ is contained in the support of $R$, with at least one support position removed. It is therefore a proper subset. $\square$

This proves the residual-matrix invariant directly: after a subtraction, the new matrix remains nonnegative and has one common row and column sum, now reduced from $r$ to $r-\alpha$. The support strictly shrinks at every step. These are separate guarantees: equal sums allow another positive permutation diagonal if the residual is nonzero; strict support loss guarantees that the process cannot continue indefinitely.

Worked Subtractions

Worked Example: Two Selected Entries Attain the Minimum

Let $R$ be the following matrix, with rows and columns indexed by $1,2,3$:

R= \begin{pmatrix} \frac12&\frac12&0\\ 0&\frac13&\frac23\\ \frac12&\frac16&\frac13 \end{pmatrix}.

The row sums are $1/2+1/2+0=1$, $0+1/3+2/3=1$, and $1/2+1/6+1/3=1$. The column sums are $1/2+0+1/2=1$, $1/2+1/3+1/6=1$, and $0+2/3+1/3=1$. So $R$ is doubly stochastic.

Choose the diagonal positions $(1,1),(2,2),(3,3)$. Their entries are $1/2,1/3,1/3$, so $\alpha=\min\{1/2,1/3,1/3\}=1/3$. Subtract $1/3$ from those three positions only:

R'= \begin{pmatrix} \frac12-\frac13&\frac12&0\\ 0&\frac13-\frac13&\frac23\\ \frac12&\frac16&\frac13-\frac13 \end{pmatrix} = \begin{pmatrix} \frac16&\frac12&0\\ 0&0&\frac23\\ \frac12&\frac16&0 \end{pmatrix}.

Each row now sums to $1/6+1/2=2/3$, $0+0+2/3=2/3$, and $1/2+1/6+0=2/3$. The columns sum to $1/6+0+1/2=2/3$, $1/2+0+1/6=2/3$, and $0+2/3+0=2/3$. Both selected entries $(2,2)$ and $(3,3)$ have disappeared from the support because both attained the minimum.

Check: $R'+\frac13 I=R$, since adding $1/3$ back to each diagonal entry of $R'$ gives $1/2,1/3,1/3$, respectively, and leaves all other entries unchanged. The residual row sum is $1-1/3=2/3$, as computed directly.

Worked Example: A Permutation Diagonal That Is Not the Main Diagonal

Let

R= \begin{pmatrix} 0&\frac23&\frac13\\ \frac12&0&\frac12\\ \frac12&\frac13&\frac16 \end{pmatrix}.

The row sums are $0+2/3+1/3=1$, $1/2+0+1/2=1$, and $1/2+1/3+1/6=1$. The column sums are $0+1/2+1/2=1$, $2/3+0+1/3=1$, and $1/3+1/2+1/6=1$. Choose positions $(1,2),(2,1),(3,3)$. They use one position in each row and column, and their entries are $2/3,1/2,1/6$. Thus $\alpha=\min\{2/3,1/2,1/6\}=1/6$.

Subtract $1/6$ from those selected positions:

R'= \begin{pmatrix} 0&\frac23-\frac16&\frac13\\ \frac12-\frac16&0&\frac12\\ \frac12&\frac13&\frac16-\frac16 \end{pmatrix} = \begin{pmatrix} 0&\frac12&\frac13\\ \frac13&0&\frac12\\ \frac12&\frac13&0 \end{pmatrix}.

The row sums are $0+1/2+1/3=5/6$, $1/3+0+1/2=5/6$, and $1/2+1/3+0=5/6$. The column sums are $0+1/3+1/2=5/6$, $1/2+0+1/3=5/6$, and $1/3+1/2+0=5/6$. The selected entry at $(3,3)$ becomes zero, so at least that support position disappears.

Check: Adding $1/6$ back at $(1,2),(2,1),(3,3)$ recovers $2/3,1/2,1/6$, respectively; every other entry is unchanged. The common row and column sum is $1-1/6=5/6$, matching the direct sums.

Worked Example: A Subtraction Can Remove More Than One Support Entry

Consider the doubly stochastic matrix

R= \begin{pmatrix} \frac35&\frac25\\ \frac25&\frac35 \end{pmatrix}.

Each row sums to $3/5+2/5=1$, and each column sums to $3/5+2/5=1$. Choose the main diagonal, with selected entries $3/5,3/5$. Their minimum is $\alpha=3/5$. The subtraction gives

R'= \begin{pmatrix} \frac35-\frac35&\frac25\\ \frac25&\frac35-\frac35 \end{pmatrix} = \begin{pmatrix} 0&\frac25\\ \frac25&0 \end{pmatrix}.

Each row sum and each column sum is $2/5$. Both selected entries attain the minimum, so two support positions disappear at once. The two off-diagonal entries remain positive and unchanged.

Check: Adding $(3/5)I$ to $R'$ recovers $R$. The common residual sum is $1-3/5=2/5$, equal to each directly calculated row and column sum.

Why Repeated Subtraction Terminates

Starting with a doubly stochastic matrix $A$, the invariant permits the subtraction to be repeated whenever the current common sum is positive. The lemma supplies a positive permutation diagonal at each such stage. The theorem then gives a new nonnegative residual with equal row and column sums, and strictly fewer positive entries.

Corollary: Repeated minimum-entry subtraction from a doubly stochastic $n\times n$ matrix terminates after finitely many steps. The original matrix is a sum $\sum_{k=1}^{q}\alpha_kP_{\pi_k}$, where every $\alpha_k>0$, every $P_{\pi_k}$ is a permutation matrix, and $\sum_{k=1}^{q}\alpha_k=1$.

Proof. Let $R_0=A$, whose common row and column sum is $r_0=1$. At step $k$, if $r_{k-1}>0$, choose a positive permutation diagonal as guaranteed by the lemma, let $\alpha_k$ be its smallest selected entry, and set $R_k=R_{k-1}-\alpha_kP_{\pi_k}$. By the theorem, $R_k$ is nonnegative, its common row and column sum is $r_k=r_{k-1}-\alpha_k$, and its support has fewer positions than the support of $R_{k-1}$.

The initial support has at most $n^2$ positions, and its size is a nonnegative integer. Since each step removes at least one support position and adds none, there can be at most $n^2$ steps. If the process stops, its common sum cannot be positive: if it were positive, the lemma would supply another positive permutation diagonal and the theorem another subtraction. Thus the final common sum is zero. Nonnegativity then implies that the final residual matrix is the zero matrix.

After $q$ steps, the successive subtraction equations give $A=\sum_{k=1}^{q}\alpha_kP_{\pi_k}+R_q$. Since $R_q=0$, this is the claimed matrix sum. In any fixed row, each permutation matrix contributes exactly one $1$, so the row sum of the sum is $\sum_{k=1}^{q}\alpha_k$. That row sum equals the row sum of $A$, which is $1$. Therefore $\sum_{k=1}^{q}\alpha_k=1$. $\square$

Common Pitfall: Subtracting More Than the Minimum

The subtraction amount must not exceed any selected entry. For example, in the first worked example, the main-diagonal entries are $1/2,1/3,1/3$. If one incorrectly subtracts $1/2$ from all three, the new selected entries would be $1/2-1/2=0$, $1/3-1/2=-1/6$, and $1/3-1/2=-1/6$. The negative entries violate the nonnegativity invariant.

The correction is to use the minimum selected entry, $1/3$, not the largest one. Then the selected entries become $1/2-1/3=1/6$, $1/3-1/3=0$, and $1/3-1/3=0$, all nonnegative. Another error is to subtract from every matrix entry: the operation is $\alpha P_\pi$, so only the one selected position in each row and each column is changed. Unselected entries must remain exactly as they were.

The subtraction step matters because it provides both a valid residual and a measure of progress. Equal row and column sums make the next selection possible; a disappearing support entry makes endless repetition impossible. Together, these facts explain why this local operation can build a finite permutation-matrix decomposition.

Check Your Understanding

Use the invariant and the minimum-entry rule to answer the following questions.

A nonnegative $3\times3$ matrix has every row and column sum equal to $r>0$. Explain why its support satisfies Hall’s condition.
In a subtraction step, why does every row sum decrease by exactly $\alpha$, even when selected entries have different values?
If two or more selected entries attain the minimum, what happens to each of them, and what does this imply about support loss?
Why can a nonnegative residual matrix with common row sum zero contain no positive entry?
Why does the sum of the subtraction coefficients equal $1$ when the starting matrix is doubly stochastic?