Linear upper-bound conjecture for the SIA-index

About 9 years old · traced to

Let nn be a positive integer and let S\mathcal{S} be an SIA set of n×nn \times n stochastic matrices. Its SIA-index is the length of the shortest SIA product formed from matrices in S\mathcal{S}. Linear upper-bound conjecture. The SIA-index of a set of n×nn \times n stochastic matrices is bounded by 2n2n. This would substantially improve the known cubic upper bound and would be consistent with the linear lower-bound evidence described in the paper. The conjecture remains open in the supplied source.

References

Primary source

Pierre-Yves Chevalier, Vladimir V. Gusev, Raphaël M. Jungers and Julien M. Hendrickx, “Sets of Stochastic Matrices with Converging Products: Bounds and Complexity”, arXiv:1712.02614 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.