Databases
StackOverflow2013
Postsdbo
POundecomposability of a non-negative integer matrix
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POundecomposability of a non-negative integer matrix
    primarykey
    data
    text
    <p>I am looking for an algorithm to test whether a non-negative dxd integer matrix is undecomposable. I call a matrix <em>undecomposable</em> if it can not be written as a product of two non-negative dxd integer matrices none of them being a permutation matrix (ie not invertible in the semiring of non-negative integer matrices SL_d(N)). I am mostly interested in the case of 3x3 matrices with determinant 1. Note that the case of 1x1 matrices correspond to ask wether a positive integer is prime. For the case of 2x2 matrices with determinant 1 it is well known that the only non-decomposable matrices are the permutation matrices and the elementary matrices (this is because the elementary matrices generate the whole SL_2(N)). There are infinitely many known examples of undecomposable matrices in SL_3(N) (J. Rivat "Undecomposable matrices in dimension 3" appendix in Pytheas Fogg "Substitutions in Dynamics, Arithmetics and Combinatorics", Springer LNM).</p> <p>There is a naive algorithm which consists at looking at a more general factorisation of the form BC = A with B a d x k matrix and C a k x d matrix. That way we may start a recursive construction. We fill the first column of B by B0 and the first line of C by C0 in such way that B0 * C0 &lt;= A (here I mean all coefficients are smaller). Then it is enough to find B' and C' of size respectively d x (k-1) and (k-1) x d such that B' * C' = A - B0*C0. This algorithm is relatively slow!</p> <p>The equations associated to the problem are quadratic with 2 d^2 variables (d^2 for A and d^2 for B) and I want to solve them with non-negative integers. As the equations are of very special form, I guess that there might be some better way to solve them or at least to make the recursive construction more efficient.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USV. Delecroix
    1. USV. Delecroix
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POundecomposability of a non-negative integer matrix
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POundecomposability of a non-negative integer matrix
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POundecomposability of a non-negative integer matrix
      1. This table or related slice is empty.
      1. VTUpMod
    1. COCan you formalize your question a bit more? For a given matrix M you want to know if there exist matrices A and B such that M = A x B ? There is always a trivial solution A = Identity, B = M, so NO matrix is indecomposable...
      singulars
      1. POundecomposability of a non-negative integer matrix
      1. UScatchmeifyoutry
    2. CO@catchmeifyoutry Right! I mean non-trivial solution (as you would do for integer factorization). Thanks.
      singulars
      1. POundecomposability of a non-negative integer matrix
      1. USV. Delecroix
    3. COHow would you define non-trivial? Does that mean that neither A or B can be diagonal?
      singulars
      1. POundecomposability of a non-negative integer matrix
      1. USMarc Claesen
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload