0
$\begingroup$

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ (resp. $J$).

I wonder if there is a fast algorithm for finding maximal sets $I$ and $J$, $I \cap J = \emptyset$ such that $\det(A_{I,J}) = \pm 1$.

Note: Obviously, $I$ and $J$ have the same cardinal.

Improve this question
$\endgroup$
3
  • $\begingroup$ It seems unlikely that such sets $I,J$ even exists for any matrix $A\in M_n(\Bbb Z)$. Define $A_{i,j}=2$ for every $i,j\in\{1,\ldots,n\}$. Then every sub-matrix $A_{I,J}$ is singular (and so $\det(A_{I,J})=0$) except when $|I|=|J|=n-1$, in which case $\det(A_{I,J})=\det(2)=2$... (and I did not mentioned the zero matrix...) $\endgroup$
    – Surb
    Commented May 27, 2015 at 22:34
  • $\begingroup$ First, I consider $I$ and $J$ as the rows and columns that do appear in $A_{I,J}$. Thus, the maximal sets in your example are the empty ones. $\endgroup$
    – teide4
    Commented May 28, 2015 at 14:57
  • $\begingroup$ Ok sorry, I misread your question. Also I did not notice that you require $I\cap J= \emptyset$ $\endgroup$
    – Surb
    Commented May 28, 2015 at 14:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .