# How to calculate the number of bases of a Totally Unimodular matrix(TUM)?

I have been reading about TUM and my question is why the number of nonsingular $$r \times r$$ submatrices of the TU matrix $$A$$ of rank $$r$$ will give me the number of bases of $$A$$?

Recall that the definition of a TUM is as follows:

A rank r totally unimodular matrix is a matrix over $$\mathbb R$$ for which every submatrix has determinant in $$\{ 0, 1, -1 \}.$$

Could anyone explain this to me please?

• What's a base of a matrix? Commented Jan 3 at 16:07
• @joriki I meant basis sorry about that … it is the maximal linearly independent set in the matrix Commented Jan 3 at 17:36
• Well, you correctly wrote "bases", which is the plural of both "base" and "basis", so the error is on my part in assuming that you meant "base". Now my question is: What's a basis of a matrix? I see you just edited your comment to answer that question, but I don't understand the answer. Do you mean the maximal linearly independent set of rows? Or of columns? Or of what? Commented Jan 3 at 17:38
• Any of them, it does not matter, it is the rank of the matrix @joriki Commented Jan 3 at 18:16
• The number of nonsingular submatrices stays the same if we transpose the matrix, so the statement must be correct or incorrect for both rows and columns simultaneously. Maybe the definition of "basis" needs to be refined. Commented Jan 4 at 7:40

This statement is not correct in this form, unless I am misunderstanding the question. Consider the rank 1 totally unimodular matrix $$A = \begin{pmatrix} 1&1 \\ 1 & 1 \end{pmatrix}$$ It has exactly 4 nonsingular submatrices and we can find two subsets of rows (or columns) that are bases of the row (or column) space of this matrix.