{"id":"a2732d01-2666-4fe6-9581-072fa576b4af","arxiv_id":"2411.18946","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For stochastic matrices of size 2x2 and 3x3, explicit generating sets are constructed, with worst-case factor count exactly 4 in dimension 2 and at most 20 in dimension 3.","lead":"This paper identifies small sets of stochastic matrices that can be multiplied together to produce every stochastic matrix in dimensions two and three. It also proves which 3-by-3 stochastic matrices are indivisible and bounds how many factors are needed in the worst case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproved sign-pattern classification is the load-bearing step, but the classifications check out; the Eq. (13) objection in the reader report does not land.","rationale":"The paper's central claim is that the set G in Eq. (10) generates s(3) and that every element is a product of at most 20 elements of G. The proof chain is: Lemma 3 gives a divisibility criterion; Theorem 1 classifies indivisible matrices by sign pattern; Theorem 3 iterates Lemma 3 until a residual sign pattern remains, then shows each residual class lies in the semigroup generated by G, with a factor-count bound. The weakest point is indeed the sign-pattern classification, exactly as the reader identified: the paper asserts the two- and five-class enumerations without proof. I verified these enumerations by classifying the possible column-support multisets, and they are correct. The other reader objection, that Eq. (13) is a false factorization, appears to be a misreading: the matrix squared in Eq. (13) has sign pattern Y, which was already shown to be in C up to permutations, so it lies in the generated semigroup; moreover, R = (1 3) v1 v2 is a valid four-factor identity. Thus the theorem is salvageable as written and does not need the specific repair the reader suggests. The remaining legitimate issue is presentation: the finite classifications should be spelled out rather than left to the reader. This does not change the conditional verdict, since the paper would benefit from an explicit enumeration and notation cleanup, but no correctness failure was found.","tokens_in":14725,"tokens_out":51280,"duration_ms":446483,"concrete_test":"Run a brute-force enumeration of all 3x3 {0,1}-matrices with no zero column, quotient by row and column permutations, and verify: (i) exactly two classes have no containment between distinct columns unless the containing column is a unit vector, namely the identity and Eq. (5); (ii) after removing classes for which Lemma 3 gives a strict increase in zero count, exactly the five classes of Eq. (12) remain; (iii) the matrix M in Eq. (13) is a row/column permutation of C(1,1,0) in G, and R = (1 3) v1 v2 holds as matrix products.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the finite classification of sign patterns in Theorem 1 and Theorem 3. Theorem 1 asserts, without proof, that up to S3xS3 only the identity and Eq. (5) have no pair of columns comparable in the sense of Lemma 3. Theorem 3 then asserts that after removing patterns for which Lemma 3 strictly increases the zero count, only the five classes in Eq. (12) remain. If either enumeration were incomplete, the characterization of indivisible matrices, the coverage of residual cases, and the bound NG(s(3)) <= 20 would all be unsupported. The paper gives only 'one readily verifies' and 'eliminating... we are left with'. I checked the classification: residual column supports must form an antichain of equal-size nonempty subsets for Theorem 1, and the five residual support multisets are, up to relabeling, {1},{2},{3}; {1,2},{1,3},{2,3}; {3},{3},{1,2}; {3},{3},{2}; and {3},{3},{3}. This is correct, so the concern is a rigor gap, not a counterexample. The reader's separate objection to Eq. (13) does not land: the matrix M there has sign pattern {3},{3},{2}, which was already shown to lie in C up to permutations, so M is in the generated semigroup; independently R = (1 3) v1 v2 gives an explicit four-factor realization.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14992,"tokens_out":61062,"duration_ms":449184,"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":[{"comment":"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.","section":"Theorem 1, proof"},{"comment":"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.","section":"Theorem 3, proof"}],"minor_comments":[{"comment":"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.","section":"Theorem 3, upper bound proof, case 2"},{"comment":"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)'.","section":"Theorem 3, proof"},{"comment":"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.","section":"Eq (13), notation"},{"comment":"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.","section":"Abstract and Introduction"}],"recommendation":"major_revision","confidential_remarks":"The core mathematics appears sound, and the concern raised in the reader's report about Eq (13) does not withstand scrutiny: the displayed product is correct. The main gap is the omitted proof of the finite sign-pattern classifications in Theorem 1 and Theorem 3. These are easily fixable and do not constitute a counterexample. With those proofs supplied, I would support acceptance. The self-citation to [11] is not load-bearing, so there is no circularity concern. The paper fits the journal's scope well."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nThe 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 <G>^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.\n\nWho 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.","headline":"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.","tokens_in":15553,"tokens_out":5738,"would_cite":true,"duration_ms":53528,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15B51","20M10","20M13","47D03"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every 3x3 stochastic matrix is a product of at most 20 matrices from a small explicit set.","keywords":["stochastic matrices","indivisible stochastic matrices","building blocks","generators of stochastic matrices","divisibility","semigroup of stochastic matrices"],"falsifier":"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)$.","tokens_in":14470,"feed_emoji":"🎲","tokens_out":14953,"duration_ms":112433,"temperature":0.7,"pith_summary":"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.","feed_headline":"Twenty simple pieces build every 3x3 stochastic matrix","feed_subtitle":"One swap, one cycle, and a family of reset matrices cover all 3-state Markov transitions in at most 20 steps.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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$."],"forward_implications":["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$."],"supporting_citations":[{"why":"It supplies the sign-function divisibility technique and the prime non-negative-matrix example behind Eq. (5).","marker":"[8]"},{"why":"It gives the identity $\\operatorname{sgn}(BC)=\\operatorname{sgn}(\\operatorname{sgn}(B)\\operatorname{sgn}(C))$ and the Boolean-matrix prime notion used in Lemma 2.","marker":"[9]"},{"why":"It defines primes and building blocks in positive matrix semigroups and supplies the group-of-units framework used in Definitions 1 and 2.","marker":"[10]"},{"why":"It establishes that the units of the stochastic-matrix semigroup are exactly the permutation matrices.","marker":"[22]"},{"why":"It provides the analogous divisibility result for quantum channels that motivates and benchmarks the sufficient divisibility criterion.","marker":"[7]"},{"why":"It supports the diameter estimate used for generating permutation factors within the overall factor bound.","marker":"[27]"}],"fun_headline_variants":["3x3 stochastic matrices: always a 20-factor product","One swap plus three resets generate all 3x3 stochastic matrices","20 steps generate any 3x3 stochastic matrix","At most 20 factors for any 3x3 stochastic matrix"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["3x3 stochastic matrices: always a 20-factor product","One swap plus three resets generate all 3x3 stochastic matrices","20 steps generate any 3x3 stochastic matrix","At most 20 factors for any 3x3 stochastic matrix"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000666,"raw_usage":{"total_tokens":3042,"prompt_tokens":954,"completion_tokens":2088,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2016}},"tokens_in":570,"tokens_out":2088,"duration_ms":15600,"temperature":1.0,"reasoning_tokens":2016,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:46:39.803932+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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)$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the sign-function divisibility technique and the prime non-negative-matrix example behind Eq. (5)."},{"cited_title":"Linear Algebra Appl","cited_arxiv_id":null,"evidence_quote":"It gives the identity $\\operatorname{sgn}(BC)=\\operatorname{sgn}(\\operatorname{sgn}(B)\\operatorname{sgn}(C))$ and the Boolean-matrix prime notion used in Lemma 2."},{"cited_title":"Linear Algebra Appl","cited_arxiv_id":null,"evidence_quote":"It defines primes and building blocks in positive matrix semigroups and supplies the group-of-units framework used in Definitions 1 and 2."},{"cited_title":"Academic Press, New York (1979)","cited_arxiv_id":null,"evidence_quote":"It establishes that the units of the stochastic-matrix semigroup are exactly the permutation matrices."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the analogous divisibility result for quantum channels that motivates and benchmarks the sufficient divisibility criterion."},{"cited_title":"In: Proceedings of the 31st Annual Symposium on Fo undations of Computer Science, vol","cited_arxiv_id":null,"evidence_quote":"It supports the diameter estimate used for generating permutation factors within the overall factor bound."}],"review_version":1}