Generating Sets of Stochastic Matrices

Fereshte Shahbeigi; Frederik vom Ende

REVIEW 2 major objections 4 minor 1 cited by

Generating Sets of Stochastic Matrices

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every 3x3 stochastic matrix is a product of at most 20 matrices from a small explicit set.

desk verdict Solid constructive results on generating sets of 2x2 and 3x3 stochastic matrices; the load-bearing sign-pattern classification is asserted rather than proved, but it checks out and the paper deserves refereeing. read the letter →

arxiv 2411.18946 v2 pith:6A2OHI5N submitted 2024-11-28 math.RA math-phmath.MPquant-ph

Frederik vom Ende , Fereshte Shahbeigi This is my paper · ORCID

classification math.RAmath-phmath.MPquant-ph MSC 15B5120M1020M1347D03

keywords stochasticmatricesindivisiblebuildingblocksgeneratorsofdivisibilitysemigroup

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies the semigroup of stochastic matrices — real matrices with nonnegative entries whose columns sum to one, the transition matrices of finite Markov chains — and asks which small subsets generate all of them under multiplication. It proves that every $2\times 2$ stochastic matrix is a nontrivial product of two stochastic matrices, and exhibits a generating set for $s(2)$ that needs at most four factors. For $3\times 3$ stochastic matrices it gives a complete classification of the indivisible elements: up to permuting rows and columns, an indivisible matrix is exactly one whose sign pattern is the zero-diagonal, all-ones matrix. Building on that classification, it constructs an explicit finite generating set $G$ for $s(3)$ and proves every element of $s(3)$ is a product of at most 20 elements of $G$. This gives a concrete answer to a basic semigroup question and a practical bound on how many simple operations are needed to implement an arbitrary three-state Markov transition.

What carries the argument

The load-bearing object is the entrywise sign map $\operatorname{sgn}$, which turns the infinite semigroup $s(n)$ into the finite set $\operatorname{sgn}(s(n))$ of sign patterns; the identity $\operatorname{sgn}(BC)=\operatorname{sgn}(\operatorname{sgn}(B)\operatorname{sgn}(C))$ means divisibility questions can be decided on patterns. Lemma 3 supplies a constructive sufficient divisibility criterion: if one column of $\operatorname{sgn}(A)$ dominates another coordinatewise, then $A=BC$ with $C$ a two-level elementary stochastic matrix and $B$ a stochastic matrix with strictly more zero entries. Iterating this zero-increasing factorization either reaches a permutation matrix or stops at one of the finitely many sign classes without comparable columns; Theorem 1 says that in dimension 3 the only such class is Eq. (5), and Theorem 3 dispatches the remaining classes by direct inclusion in $G$. The explicit generating set $G$ combines a transposition, a 3-cycle, and the convex hull of three reset matrices, so that permutation factors are produced in at most two steps.

What would settle it

A computer search that enumerates the 125 sign patterns in $\operatorname{sgn}(s(3))$ modulo $S_3\times S_3$ and finds any class other than the identity and Eq. (5) with no pair of comparable columns would refute Theorem 1 and, with it, the proof that $G$ generates $s(3)$.

Watch

Extended reading notes

Core claim

The central claim is that the semigroup $s(3)$ of all $3\times 3$ stochastic matrices is generated by the explicit set $G=\{P_{12}\}\cup\operatorname{conv}\{\mathbb{1},M_1,M_2,M_3\}$, and that $G^{20}=s(3)$: every $3\times 3$ stochastic matrix is a product of at most twenty elements of $G$. Here $P_{12}$ is a single two-level swap, and the convex hull consists of three-level reset matrices interpolating between the identity, a permutation, and doubly degenerate projections. The proof first characterizes indivisibility: a $3\times 3$ stochastic matrix is indivisible if and only if, up to $S_3\times S_3$, its sign pattern is the zero-diagonal all-ones matrix of Eq. (5). It then applies a divisibility lemma that splits any matrix with a coordinatewise-dominating column into two factors, one with strictly more zeros, and iterates until only finitely many sign classes remain; each leftover class is shown to lie in $G$. In two dimensions the analogous statement is stronger: every element of $s(2)$ is divisible, and the generating set from Eq. (8) satisfies $G^4=s(2)$ with $N_G(s(2))=4$.

Load-bearing premise

Everything in the $3\times 3$ classification rests on the unproven assertion that, after permuting rows and columns and deleting zero entries, only two sign patterns have no column containing another: the identity pattern and the zero-diagonal all-ones matrix of Eq. (5); if a third such pattern existed, the characterization of indivisibility and the generating set would both be incomplete.

Editorial extensions

If this is right

Every 3-state Markov transition matrix can be implemented by at most 20 operations drawn from a single two-level swap, a cyclic permutation, and a one-parameter convex family of reset operations.
The indivisible $3\times 3$ stochastic matrices are exactly the sign-equivalents of Eq. (5), so every generating set for $s(3)$ must contain a representative of that $S_3\times S_3$ class.
Because $s(n)$ is norm-bounded with submultiplicative norm 1, the bound $N_G(s(3))\le 20$ implies that approximating each generator to accuracy $\varepsilon$ yields every $3\times 3$ stochastic matrix to accuracy at most $20\varepsilon$.
In two dimensions the classification is degenerate: every $2\times 2$ stochastic matrix is divisible, and the generating set of Eq. (8) is optimal with $N_G(s(2))=4$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof of Theorem 3 is constructive enough to yield an explicit recursive algorithm that factors any 3x3 stochastic matrix into the twenty generators; the paper does not present this algorithm as pseudocode, but the case analysis in the proof determines it.
A computational enumeration of the 125 sign patterns of $\operatorname{sgn}(s(3))$ modulo $S_3\times S_3$ would mechanically verify the unproved enumeration in Theorem 1 and could be run independently of the paper's argument.
The paper's conjecture that $N_G(s(3))=20$ is tight, and its tentative $O(n^4)$ upper-bound conjecture for higher dimensions, both remain open; testing whether a similar generating set provably attains $O(n^4)$ scaling would require new ideas, because the paper notes its sign-pattern strategy stalls for $n\ge 4$.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Punchline: this paper earns its page count. It gives the first explicit generating sets for s(2) and s(3), proves the exact worst-case factor count 4 in 2D, an upper bound 20 in 3D, and a complete characterization of indivisible 3x3 stochastic matrices. I worked through the main claims: Lemma 3 is right, Proposition 2 is right, and the decomposition strategy in Theorem 3 does give the bound.

What is genuinely new: adapting sign-pattern divisibility from nonnegative matrices to stochastic matrices, and showing the residual cases reduce to five semigroup classes. The building-block framework is standard but applied cleanly. Citation pattern is fine: the prior work on nonnegative and Boolean primes is independent and load-bearing only through standard techniques; the self-citation is motivational.

The soft spots are real but not fatal. The enumeration of sign patterns in Theorem 1 and the elimination leading to the five classes in Theorem 3 are both asserted with "one readily verifies". That is the load-bearing step, and the paper does not show its work. I checked it: under the antichain requirement there really are only identity and Eq. (5) in Theorem 1, and the five residual classes in Theorem 3 are exhaustive. So the gap is rigor of presentation, not correctness.

The Eq. (13) objection in the reader report does not land as a counterexample. The displayed matrix is not in G, so if one reads the line as a claim about G^2 it is wrong. But the paper's notation is ^2_s, i.e., two elements of the generated semigroup, and the all-ones-row matrix also has an explicit four-generator realization R = (1 3) v1 v2. So that is a notation slip, not a broken theorem. Minor pi/tau ordering slips in Lemma 3 and around Eq. (14) should be cleaned up but do not affect the argument.

Who is this for: people working on Markov chain synthesis, semigroup generation, or quantum-divisibility analogies will get direct use from the constructive generating sets and the factor bound. The paper deserves serious refereeing. Send it out; ask the authors to replace the hand-waved classifications with an explicit finite enumeration and to fix the notation around Eq. (13). Conditionally accept after those revisions.

Referee Report

2 major / 4 minor

Summary. The paper studies generating sets of the semigroup s(n) of n-by-n column-stochastic matrices. It introduces notions of indivisible elements and building blocks for monoids, gives a sufficient condition for divisibility of stochastic matrices via sign-pattern comparisons (Lemma 3), and proves that in dimensions 2 and 3 this condition is also necessary: Theorem 1 classifies all indivisible 3x3 stochastic matrices up to permutation equivalence, and Proposition 2 gives a generating set for s(2) with NG(s(2)) = 4. The main result, Theorem 3, constructs an explicit generating set G for s(3) consisting of a two-level flip, a cyclic permutation, and a convex family of three reset matrices, and proves that every element of s(3) is a product of at most 20 elements of G. The proof uses an iterative division algorithm that applies Lemma 3 until reaching one of five residual sign-pattern classes, which are then handled explicitly. The paper also discusses the failure of the sign-pattern method in higher dimensions and states open problems about optimality of the bound and generalization to n ≥ 4.

Significance. If correct, the paper provides the first explicit finite universal generating set for 3x3 stochastic matrices, together with a uniform bound on the number of factors, a result that is natural and useful in semigroup theory, matrix analysis, and the classical-quantum analogy (e.g., universal sets of quantum channels). The sign-function technique gives a clean sufficient divisibility criterion that is provably necessary in small dimensions, and the notion of building blocks is a sensible addition to the theory. The paper is self-contained, does not fit any parameters, and does not rely on circular reasoning; its main results are falsifiable and explicit. The only significant weakness is that two finite classifications are asserted without proof, although they appear to be correct and are readily verifiable by a short enumeration.

major comments (2)

[Theorem 1, proof] The assertion that 'one readily verifies' that the only sign-pattern classes in sgn(s(3)) with no pair of comparable columns are the identity and the matrix in Eq (5) is load-bearing for Theorem 1 and, through the analogous elimination in Theorem 3, for the entire construction of the generating set and the bound NG(s(3)) ≤ 20. No proof or computational verification is supplied. Please provide the enumeration, for example by classifying antichains of nonempty subsets of {1,2,3} up to the action of S3 × S3, or by giving a short calculation that establishes the classification.
[Theorem 3, proof] The enumeration in Eq (12) of the five residual equivalence classes after eliminating matrices that satisfy the strict-zero-increase condition of Lemma 3 is stated without proof ('Eliminating those elements ... we are left with the following five equivalence classes'). This step is load-bearing for the proof of ⟨G⟩s = s(3) and for the upper bound. The authors should supply a concise argument showing that these five classes are indeed all that remain (for instance, by listing the possible column-support multisets after applying the elimination criterion), or relegate the verification to a supplementary file. Without such a proof, the main theorem is not fully established.

minor comments (4)

[Theorem 3, upper bound proof, case 2] In the case where Bmπm is the matrix N of Eq (13), the statement 'hence A = π1 g1 g2 π2' is correct but terse. It would be clearer to state explicitly that the only stochastic matrices with the sign pattern {3},{3},{3} are, up to row permutation, exactly N = e3(1,1,1)^T, and that N absorbs any stochastic matrix on the right, so A is itself a permutation of N and can be written as P v1 v2 Q with two permutations and two elements of the convex hull.
[Theorem 3, proof] The phrase 'if Bmπm were matrix (13)' is confusing because Eq (13) is a display of the factorization of the third matrix in (12), not a matrix in the list. Please rephrase, e.g., 'if Bmπm were the third matrix in (12)'.
[Eq (13), notation] The notation ⟨G⟩s^2 = ⟨G⟩s is correct because the generated semigroup is a monoid containing the identity, but it may be unclear on first reading; a brief parenthetical that S^2 = S for any monoid would help.
[Abstract and Introduction] The abstract would benefit from a concrete statement of the main result (e.g., the explicit G in Eq (10) and the bound 20) instead of only describing the concepts. As is, the abstract does not convey the paper's central contribution until the body is read.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the generating-set construction and factor bound are derived from independent divisibility criteria, not from assumptions equivalent to the conclusion.

full rationale

The paper's central claim, that the set G in Eq. (10) generates s(3) with at most 20 factors, is not circular. The divisibility Lemma 3 is an adaptation of the independent Richman-Schneider result for nonnegative matrices, and Theorem 1's sign-pattern classification is an unproved but checkable finite enumeration, not an input to itself. The five residual sign classes in Eq. (12) are obtained by eliminating classes to which Lemma 3 strictly increases zeros; they are output of the derivation, not built into G by definition. The proof then shows each residual class lies in the semigroup generated by G, either as a permutation, as an indivisible class covered by the convex hull, or via an explicit identity such as Eq. (13). The self-cited reference [11] is used only as motivation for the building-block concept and does not support any theorem, so it is not load-bearing. No parameters are fitted and no prediction reduces to its inputs. The main rigor caveat is the unproved 'one readily verifies' enumeration in Theorem 1, but incompleteness there would be a correctness gap, not circularity; the enumeration itself is not assumed in the theorem's statement. Overall, the derivation is self-contained with respect to the external benchmarks cited.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard semigroup theory, the sign identity, and a cited primality result for a specific Boolean matrix. There are no fitted parameters and no newly postulated physical entities. The only unproved internal claim is the finite sign-pattern classification in Theorem 1.

assumptions (4)

domain assumption The group of units of s(n) is the symmetric group S_n acting by permutation matrices.
Standard fact cited to [22]; used to define indivisibility and building blocks in Section 2.
standard math For all nonnegative matrices B,C, sgn(BC) = sgn(sgn(B)sgn(C)).
Proved in Section 3.1 (Eq (4)); used in Lemma 2 and Theorem 1.
standard math The matrix M in Eq (5) is prime in the semigroup of Boolean 3x3 matrices and in R^{3x3}_+.
Cited to [8,9]; needed for the indivisible direction of Theorem 1.
ad hoc to paper Modulo S3 x S3, the only sign patterns in sgn(s(3)) with no pair of columns where one support contains another are the identity and M.
Asserted as 'one readily verifies' in the proof of Theorem 1; the enumeration is not shown and all later classification depends on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Generating Sets of Stochastic Matrices." pith.science (2026). https://pith.science/paper/6A2OHI5N

@misc{pith2026241118946,
  author       = {Pith},
  title        = {Pith review of: Generating Sets of Stochastic Matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6A2OHI5N}},
  note         = {Machine review of arXiv:2411.18946}
}

abstract

This paper introduces the concept of a generating set for stochastic matrices -- a subset of matrices whose repeated composition generates the entire set. Understanding such generating sets requires specifying the "indivisible elements" and "building blocks" within the set, which serve as fundamental components of the generation process. Expanding upon prior studies, we develop a framework that formalizes divisibility in the context of stochastic matrices. We provide a sufficient condition for divisibility that is shown to be necessary in dimension $n=3$, while for $n=2$, all stochastic matrices are shown to be divisible. Using these results, we construct generating sets for dimensions 2 and 3 by specifying the indivisible elements, and, importantly, we give an upper bound for the number of factors required from the generating set to produce the entire semigroup.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Divisible and indivisible Stochastic-Quantum dynamics
quant-ph 2025-05 conditional novelty 7.0 of 10

A two-state stochastic evolution is divisible between given times if and only if the earlier transition matrix lies in one of two explicitly described cone regions, with continuous curves crossing a critical diagonal ...

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · cited by 1 Pith paper

[1]

Cambridge Series in Statistical and Pr obabilistic Mathematics

Norris, J.R.: Markov Chains. Cambridge Series in Statistical and Pr obabilistic Mathematics. Cambridge University Press, Cambridge (1997)

work page 1997
[2]

Cambridge University Press, C ambridge (2012)

Heinosaari, T., Ziman, M.: The Mathematical Language of Quantum Theory: From Uncertainty to Entanglement. Cambridge University Press, C ambridge (2012)

work page 2012
[3]

Springer, Cham (2024)

Privault, N.: Discrete Stochastic Processes: Tools for Machine L earning and Data Science. Springer, Cham (2024)

work page 2024
[4]

Linear Algebra Appl

Gow, R., Tamburini, M.: Generation of SL(n, Z ) by a Jordan Unipotent Matrix and Its Transpose. Linear Algebra Appl. 181, 63–71 (1993)

work page 1993
[5]

Semigroup F orum 51, 319–333 (1995)

Rus ˇkuc, N.: Matrix Semigroups–Generators and Relations. Semigroup F orum 51, 319–333 (1995)

work page 1995
[6]

Braun, D., Giraud, O., Nechita, I., Pellegrini, C., ˇZnidariˇ c, M.: A Universal Set of Qubit Quantum Channels. J. Phys. A 47, 135302 (2014)

work page 2014
[7]

Wolf, M., Cirac, J.: Dividing Quantum Channels. Commun. Math. Phys . 279, 147–168 (2008)

work page 2008
[8]

Richman, D., Schneider, H.: Primes in the Semigroup of Non-Negativ e Matrices. Lin. Multilin. Alg 2, 135–140 (1974)

work page 1974

Show all 27 references

[9]

Linear Algebra Appl

de Caen, D., Gregory, D.: Primes in the Semigroup of Boolean Matric es. Linear Algebra Appl. 37, 119–134 (1981) 16

1981
[10]

Linear Algebra Appl

Picci, G., Hof, J., Schuppen, J.: Primes in Several Classes of the P ositive Matrices. Linear Algebra Appl. 277, 149–185 (1998)

1998
[11]

arXiv:2407.17103, to appear in J

vom Ende, F.: A Suﬃcient Criterion for Divisibility of Quantum Chann els. arXiv:2407.17103, to appear in J. Math. Phys. (2024)

2024 arXiv
[12]

Cambridge University Pre ss, Cambridge (1987)

Sharpe, D.: Rings and Factorizations. Cambridge University Pre ss, Cambridge (1987)

1987
[13]

Rocky Mt

Anderson, D., Valdes-Leon, S.: Factorization in Commutative Rin gs With Zero Divisors. Rocky Mt. J. Math. 26, 439–480 (1996)

1996
[14]

Clarendon Press, Oxford (1989)

Hilgert, J., Hofmann, K.-H., Lawson, J.D.: Lie Groups, Convex Con es, and Semigroups. Clarendon Press, Oxford (1989)

1989
[15]

Linear Algebra Appl

Hof, J., Schuppen, J.: Positive Matrix Factorization via Extrema l Polyhedral Cones. Linear Algebra Appl. 293, 171–186 (1999)

1999
[16]

Academic Press , London (1976)

Davies, E.B.: Quantum Theory of Open Systems. Academic Press , London (1976)

1976
[17]

In: Wendland, W., Efendiev, M

Hackl, K., Mielke, A., Mittenhuber, D.: Dissipation Distances in Multip licative Elastoplasticity. In: Wendland, W., Efendiev, M. (eds.) Analysis and S imulation of Multiﬁeld Problems, pp. 87–100. Springer, Berlin, Heidelberg (200 3)
[18]

arXiv:math/0207198 (2002)

Mittenhuber, D.: The Dissipation Distance for a 2D Single Crystal With Two Symmetric Slip Systems. arXiv:math/0207198 (2002)

2002 arXiv
[19]

Cambridge University Press, Cambridge (20 10)

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum In formation, 10th anniversary edn. Cambridge University Press, Cambridge (20 10)
[20]

Albertini, F., D’Alessandro, D.: Analysis of Quantum Walks With Time- Varying Coin on d-Dimensional Lattices. J. Math. Phys. 50, 122106 (2009)

2009
[21]

Albertini, F., D’Alessandro, D.: Controllability of Quantum Walks on G raphs. Math. Control Signals Syst. 24, 321–349 (2012)

2012
[22]

Academic Press, New York (1979)

Berman, A., Plemmons, R.: Nonnegative Matrices in the Mathemat ical Sciences. Academic Press, New York (1979)

1979
[23]

Marcus, M., Kidman, K., Sandy, M.: Products of Elementary Doub ly Stochastic Matrices. Lin. Multilin. Alg 15, 331–340 (1984)

1984
[24]

Lin ear Algebra Appl

Cho, H., Kim, S.-R.: Factorizations of Matrices Over Semirings. Lin ear Algebra Appl. 374, 289–296 (2003)

2003
[25]

Borosh, I., Hartﬁel, D., Maxson, C.: Answers to Questions Pose d by Richman and Schneider. Lin. Multilin. Alg. 3, 255–258 (1976) 17

1976
[26]

Schroeder, M.: Fractals, Chaos, Power Laws: Minutes from an Inﬁnite Paradise. W. H. Freeman and Company, New York (1991)

1991
[27]

In: Proceedings of the 31st Annual Symposium on Fo undations of Computer Science, vol

Babai, L., Hetyei, G., Kantor, W., Lubotzky, A., Seress, A.: On th e Diameter of Finite Groups. In: Proceedings of the 31st Annual Symposium on Fo undations of Computer Science, vol. 2, pp. 857–865. IEEE Computer Society, L os Alamitos, CA, USA (1990) 18

1990

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Cambridge Series in Statistical and Pr obabilistic Mathematics

Norris, J.R.: Markov Chains. Cambridge Series in Statistical and Pr obabilistic Mathematics. Cambridge University Press, Cambridge (1997)

work page 1997

[2] [2]

Cambridge University Press, C ambridge (2012)

Heinosaari, T., Ziman, M.: The Mathematical Language of Quantum Theory: From Uncertainty to Entanglement. Cambridge University Press, C ambridge (2012)

work page 2012

[3] [3]

Springer, Cham (2024)

Privault, N.: Discrete Stochastic Processes: Tools for Machine L earning and Data Science. Springer, Cham (2024)

work page 2024

[4] [4]

Linear Algebra Appl

Gow, R., Tamburini, M.: Generation of SL(n, Z ) by a Jordan Unipotent Matrix and Its Transpose. Linear Algebra Appl. 181, 63–71 (1993)

work page 1993

[5] [5]

Semigroup F orum 51, 319–333 (1995)

Rus ˇkuc, N.: Matrix Semigroups–Generators and Relations. Semigroup F orum 51, 319–333 (1995)

work page 1995

[6] [6]

Braun, D., Giraud, O., Nechita, I., Pellegrini, C., ˇZnidariˇ c, M.: A Universal Set of Qubit Quantum Channels. J. Phys. A 47, 135302 (2014)

work page 2014

[7] [7]

Wolf, M., Cirac, J.: Dividing Quantum Channels. Commun. Math. Phys . 279, 147–168 (2008)

work page 2008

[8] [8]

Richman, D., Schneider, H.: Primes in the Semigroup of Non-Negativ e Matrices. Lin. Multilin. Alg 2, 135–140 (1974)

work page 1974