3
$\begingroup$

Given an $m\times n$ matrix $\mathbf{A}$ $(m\gneqq n)$, I'm trying to efficiently find all $n\times n$ invertible submatrices using a computer. Equivalently, I'm trying to find which rows of $\mathbf{A}$ can form a linearly-independent set.

As an approach, I know I can iterate over all $m \choose n$ submatrices and compute their determinant, but I am hoping for a more efficient route. I thought about iteratively building up a solution, say starting by considering all solutions that include the first row. However, I don't know how to compute whether a set of fewer than $n$ vectors in $\mathbb{R}^n$ is linearly independent. (If it's exactly $n$ vectors, you test whether the determinant is zero or not; if it's more than $n$ vectors, it's obviously dependent; but if it's fewer, what do you do? Is there an algorithm?)

I am not sure I understand enough about linear algebra and properties of the null space to know how to compute these subsets efficiently. Any help would be appreciated.


Context #1 : The matrix $\mathbf{A}$ is not just any matrix. In my application, it's the null space of a particular matrix $\mathbf{B}$. So I am actually looking for the invertible submatrices $\mathrm{ null}(\mathbf{B})$.

Context #2: If it helps, I am working with a specific type of matrix useful for solving "number-tower puzzles". The objective of the number-tower puzzle is to fill in numbers in a given triangular structure so that every number is equal to the sum of the two numbers below it. Some numbers are specified in advance, providing constraint. Example:

enter image description here

I wondered how many blocks (and which blocks) you had to specify in advance in order for the problem to be uniquely solvable. Because we're dealing with a sum constraint, we can express this as a matrix property. And because the $n$ nodes in the bottom row uniquely determine the solution, we know that it will always take exactly $n$ independent entries to uniquely determine the solution. But which of these blocks are independent?

A tower with $n$ blocks in the base has $n(n+1)/2$ total blocks. We can form an "ancestral path" matrix $\mathbf{A}$ with $n(n+1)/2$ rows and $n$ columns. Entry $i,j$ is the number of upward paths to node $i$ from the base node $j$. (Equivalently, the $j$th column of $\mathbf{A}$ lists the values of all the blocks in the pyramid when the $j$th base block has value 1, and all the other base blocks have value 0— a kind of basis set.) If you form a submatrix $\mathbf{D}$ by extracting $n$ rows of $\mathbf{A}$ (corresponding to $n$ blocks in the pyramid), those $n$ blocks may be filled out independently if and only if $\mathbf{D}$ is invertible. The question is then— how do you find all possible such submatrices?

Perhaps the triangular form of the tower offers some simplification, but I'm not sure.

$\endgroup$
  • 2
    $\begingroup$ Maybe you can use Gram-Schmidt: iff a new added to a set vector orthonormalizes to $0$, it's linearly dependent with the set. You can pass the orthonormalized set to your recursive rotune which select a new vector or not. $\endgroup$ – Alexey Burdin Jul 22 at 0:06
1
$\begingroup$

Updated Answer:

I would appreciate it if others double check this to make sure everything is correct, I would warn the reader there may be errors:

Important: I just realized that there are in fact invertible square matrices which are not triangular. Since any square matrix over the field of complex numbers can be conjugated to triangular matrices, so this approach could still be of use. I am not sure if this a good starting point for the question now that we are restricted to a field over the complex numbers, I'm going to leave this up in case it is of use to the OP or anyone else who wants to answer the question

--

I'm denoting the orignal m x n matrix B

Triangularize your n x n matrix A which is arbitrary if I understand the question correctly...

Then, we can put A in a matrix with abritrary m-n columns from B inserted into this matrix on the right side of A, such that (*) are nonzero, and * are either zero or nonzero. We'll call this new matrix C.

\begin{bmatrix}(*)&*&*&*&*&*&*&.&.&.&*\\0&(*)&*&*&*&*&*&.&.&.&*\\0&0&(*)&*&*&*&*&.&.&.&*\\0&0&0&(*)&*&*&*&.&.&.&*\\0&0&0&0&(*)&*&*&.&.&.&*\\0&0&0&0&0&(*)&*&.&.&.&*\end{bmatrix}

Note that this immediately implies that A, your n x n invertible matrix, will exist if and only if there exists a nonzero entry in each row of C!

A is thus an n x n triangular matrix with nonzero entries along the diagonal.

We can also determine at most how many A's are possible given B if C - A is a square triangular matrix with nonzeroes on the diagonal additionally with each column of C - A ≠ any column in A.. I haven't done the general case yet but I would be interested in seeing what it is if anyone else wants to try, as a general formula for the number of A's that exist may complete the answer.

Due to the conditions of C, A will still be invertible if we interchange any number of columns of A with the corresponding columns in C - A.

If we restrict the interchanging operation to just one column, we have (m - n) + 1 possible A's. We add the 1 as A, unchanged, is invertible.

If we restrict the interchanging operation to two columns, we have $(m - n) / 2 + 1$ possible A's

Continuing $m - n$ times,

There exist at most $$ y = \biggl(\sum_{i=1}^{m-n} \frac{m-n}{i}\biggr) + 1 $$

possible A's, given the conditions we set for C - A

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks! I want to clarify that I'm looking specifically for the invertible matrices you can form by picking out some rows of the matrix $\mathbf{A}$. There's a finite number of ways to do that, so I'm not sure the concept of basis or vector space applies. (This is different from finding an infinite collection of invertible matrices). $\endgroup$ – user326210 Jul 22 at 1:14
  • $\begingroup$ I'm not sure I understand what you're looking for then. Could you reword your question? It sounds like you're looking for a formula that will generate invertible matrices. A possible answer is a minimal set of matrices, with which you can take combinations of, and obtain all of the invertible matrices. Similar to a basis, it would be some sort of set that "generates" all possible matrices. The Gram Schmidt algorithm would probably be similar to what you're looking for in how to create this L.I. set, given the L.D. set. Perhaps this would help: en.wikipedia.org/wiki/General_linear_group $\endgroup$ – diracsum Jul 22 at 2:29
  • 1
    $\begingroup$ I have a fixed $m\times n$ matrix. You can pick $n$ rows out of that matrix and delete the rest. The result is an $n\times n$ matrix, which might be invertible or might not. I'm wondering which rows you can pick such that the result of this process is an invertible matrix. $\endgroup$ – user326210 Jul 22 at 2:32
  • $\begingroup$ Oh I think I have a better understand of your question now. You need to create a linearly independent set of length n for your new matrix A from the original set of length m. Then, A will be invertible. Perhaps this will help: A will be an triangular matrix (en.wikipedia.org/wiki/Triangular_matrix). Your solution, A, will not necessarily be unique. Let me know if that helps! $\endgroup$ – diracsum Jul 22 at 2:54
  • 1
    $\begingroup$ Thanks! Yes, I am looking for all possible matrices A, so not necessarily unique. Why will A be triangular? $\endgroup$ – user326210 Jul 25 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.