Canonical decomposition of a 3x3 semi-magic square

Every $3\times3$ semi-magic square with nonnegative integer entries and line sum $t$ can be written uniquely as a nonnegative integer combination

of the six order-three permutation matrices, normalized by $\min(x,y,z)=0$. Here $D,E,F$ are the three even transversals (the identity and the two $3$-cycles) and $A,B,C$ the three odd ones (the transpositions).

Existence. Put $u=\min D$, $v=\min E$, $w=\min F$ and subtract $uD+vE+wF$; the residual $M'$ is again semi-magic and each of its three even transversals has minimum $0$. Writing $M'$ in the four-parameter form

the three vanishing minima read

If $b>c$ then each of the three ways for the middle minimum to vanish forces the opposite inequality: $b=0$ is impossible, $t'-c-d=0$ gives $c+d=t'$ and hence $b\le c$ from $b+d\le t'$, and $t'-a-c=0$ gives $a+c=t'$ and hence $b\le c$ from $a+b\le t'$. So $b\le c$, and symmetrically $c\le b$; thus $b=c$, which is exactly the statement that $M'$ is a combination of $A,B,C$ alone.

Uniqueness. The normalization is essential: without it the single relation $D+E+F=A+B+C$ (both sides equal the all-ones matrix) would identify distinct $6$-tuples. With $\min(x,y,z)=0$ the coefficients are recovered from $M$ by $u=\min D$, $v=\min E$, $w=\min F$ and $x=M_{00}-u$, $y=M_{11}-u$, $z=M_{01}-v$.

Formalization Note sm3Of is defined over $\mathbb{N}$ with truncated subtraction where necessary, so every recovery identity has to be stated with the admissibility inequalities as explicit hypotheses.