bibkey: vomendeshahbeigi2024stochasticgenerators
authors: Frederik vom Ende; Fereshte Shahbeigi
year: 2024
title: "Generating Sets of Stochastic Matrices"
doi: null
url: https://arxiv.org/abs/2411.18946v2
claim: "Theorem 3 asserts that the set G of Eq. (10), the swap of the first two levels together with the convex hull of the identity and three explicit matrices, generates the 3 × 3 column-stochastic matrices with G^20 = s(3); the authors conjecture that the bound N_G(s(3)) ≤ 20 is optimal."
strata_touched:
  - D5/S3/Quantum/Matrix/StochasticGeneratorSetRefutation
license: citation-only
triage: anchor

vom Ende and Shahbeigi, generating sets of stochastic matrices

F. vom Ende and F. Shahbeigi, Generating Sets of Stochastic Matrices, arXiv:2411.18946 [math.RA, cross-listed math-ph and quant-ph] (v1 28 November 2024; v2 1 February 2025). The arXiv comments read “18 pages, submitted to Semigroup Forum, comments welcome”; the arXiv record lists no DOI or journal reference.

Verified locator

Primary version read: https://arxiv.org/abs/2411.18946v2; the text was read from the PDF.

• §2, page 4: the definition of s(n) as the column-stochastic matrices;
• §2, Definition 3 (page 5): N_G(x) and N_G(S);
• §3.1, Lemma 3 (page 8) and Theorem 1 (page 10): the division lemma and the classification of indivisible elements of s(3);
• §3.2, Theorem 3 with Eq. (10) and its proof (pages 12–14);
• §4, Outlook (page 15): the conjecture.

Source statements

§2: “the n × n (column-)stochastic matrices, denoted by s(n), are those A ∈ R^{n×n} which satisfy a_jk ≥ 0 for all j, k = 1, . . . , n, as well as Σ_{j=1}^n a_jk = 1 for all k = 1, . . . , n.”

Definition 3: “Given a monoid (S, ∘), a generating set G ⊆ S, and any x ∈ S, we define N_G(x) as the smallest possible number of elements from G one needs to generate x. Formally, N_G(x) := min{m : ∃ x_1, . . . , x_m ∈ G x = x_1 ∘ . . . ∘ x_m}. Moreover, we define N_G(S) := sup_{x∈S} N_G(x).”

Theorem 1: “Given A ∈ s(3), A is indivisible if and only if there exist π, τ ∈ S3 such that π sgn(A) τ = [[0, 1, 1], [1, 0, 1], [1, 1, 0]].”

Theorem 3: “The semigroup generated by G := {[[0, 1, 0], [1, 0, 0], [0, 0, 1]]} ∪ conv{1, [[1, 0, 1], [0, 1, 0], [0, 0, 0]], [[1, 0, 1], [0, 0, 0], [0, 1, 0]], [[0, 0, 1], [1, 0, 0], [0, 1, 0]]} (10) equals s(3) with G^20 = s(3), i.e., N_G(s(3)) ≤ 20 as the number of factors from G needed to obtain any stochastic matrix is upper bounded by 20.”

Proof of Theorem 3: the convex hull in (10) equals “C := {[[a, 0, 1 − c], [1 − a, b, 0], [0, 1 − b, c]] : a, b, c ∈ [0, 1], a ≥ b ≥ c}”, and “for every A ∈ s(3) with sgn(A) ∈ {π [[0, 1, 1], [1, 0, 1], [1, 1, 0]] τ : π, τ ∈ S3} there certainly exist permutations π_A, τ_A ∈ S3 such that π_A A τ_A ∈ C.”

§4: “First, is the upper bound N_G(S) ≤ 20 in Theorem 3 optimal? We conjecture that this is true, seeing how this number corresponds to a factorization A = π_0 ∏_{i=1}^6 g_i π_i, π_i ∈ S_n, g_i ∈ (11) alternating between permutations and two-level transformations”.

Reading used by the repository

G^m is the set of products of m elements of G, with G^0 = {1}; since 1 ∈ G, G^m ⊆ G^{m+1}. For the G of Eq. (10), the conjecture together with Theorem 3 asserts N_G(s(3)) = 20, that is, G^20 = s(3) and G^19 ≠ s(3).