2
$\begingroup$

Problem: Let $A$ be a $n \times n$ integer matrix, $\det(A) = \pm 1$. Under which conditions there exist a nested sequence of principal submatrices of size $n$ such that they all have determinant $\pm 1$ ?

We call such a sequence a $\pm 1$ Principal Minor Sequence ($\pm 1$PMS). Note that such a sequence is described by a permutation of $n$ elements. For example, consider the matrix $$ A = \left[ \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{array} \right]. $$ The sequence $(1,2,3)$ $$ A \left[ 1 \right] = \left[ \begin{array}{c} 1 \end{array} \right], \quad A \left[ 1,2 \right] = \left[ \begin{array}{cc} 1 & 1\\ 1 & 1 \end{array} \right], \quad A \left[ 1,2,3 \right] = A. $$ is not a $\pm 1$PMS since $\det(A \left[ 1,2 \right])=0$. The sequence $(1,3,2)$ is a $\pm 1$PMS. On the other hand, the matrix $$ A = \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{array} \right] $$ does not have any $\pm 1$PMS.

Does anybody know if this problem has already been studied? A related problem is to estimate the number of $\pm 1$PMS of a matrix.

Note: It is trivial that a matrix has no $\pm 1$PMS if all its entries in the diagonal are zero.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Actually, some permutation have all zero entries in the diagonal. In fact, J-I has such a regular sequence where all but the 1 by 1 matrix has a zero diagonal. For any regular matrix, determinant computation by Laplace expansion will give you a sequence. In fact, it will give you at least n! many of them, if you count by original index sets. $\endgroup$
    – The Masked Avenger
    Commented Apr 18, 2015 at 18:05
  • $\begingroup$ Each time asking "Under which conditions" you should specify in what terms you want an answer. Your desired conclusion is a condition! $\endgroup$
    – Alex Degtyarev
    Commented Apr 18, 2015 at 18:11
  • 2
    $\begingroup$ repost from MSE math.stackexchange.com/questions/1240497/… (posted originally only three hours earlier, and already having two answers posted) $\endgroup$
    – Mirko
    Commented Apr 18, 2015 at 18:16
  • $\begingroup$ If you compute the adjoint of the matrix, and count the number of nonzero terms of its permanent, that number times n! is what I think is the number of sequences will be, however you may have to compute all the minors to prove this guess. $\endgroup$
    – The Masked Avenger
    Commented Apr 18, 2015 at 18:17
  • $\begingroup$ Note that this is not just a sequence of minors. They are: (1) nested; (2) "symmetric": the indices of the columns and the rows coincide; (3) "central": the diagonal of the minor lies on the diagonal of the matrix. I think that I took care enough to avoid this confusion. $\endgroup$
    – teide4
    Commented Apr 18, 2015 at 18:39

0

Reset to default

You must log in to answer this question.