Proving (or refuting) TU (totally unimodularity) of a matrix nxm

Question

I am new to Mathematica and want to prove the totally unimodularity of a matrix (not a particular one, but for any matrix input).

A matrix A is totally unimodular (TU) if every square submatrix of A has determinant −1, 0 or +1.

So far, I have calculated the determinant of my matrix. Then, I got the minors of my matrix, but since my original matrix of dimension nxm is not square, the determinant minors are not necessarily square matrices.

Disclaimer: This is not for homework or a test, but for my own project. And I also want to learn mathematica for future stuff because I think it is an astonishing tool for future works I would like to explore.

Answer 1

EDIT 1: thanks to the user @orpanter, author of the OP, for running the diagnostics and checking that the suggested solution indeed works correctly.

We code in a matrix

matrix = {{1, 2, 3, 4}, {7, 8, 9, 10}, {5, 4, 3, 2}, {11, 9, 6, 
    5}, {12, 13, 3, 4}, {1, 0, 14, 4}};

with Dimensions given by

matrix // Dimensions

{6, 4}

From the documentation, we know that Subsets gives a list of all possible subsets of list.

subsets = Subsets[matrix];

From the above sublists, we keep only the ones that are square

res = Select[subsets, SquareMatrixQ[##] &];

and then we calculate their determinants

Det /@ res

{0, 0, 0, -66, 36, -594, -66, 36, -594, -1375, -132, 72, -1188, -2593, 157}

Edit 2: substantial edit

After the comments, the matrix we consider here is given by:

matrix = {{1, 1, 1, 1, 0, 0, 0}, {1, 0, 0, 0, 1, 1, 1}, {0, -1, 0, 0, 
    1, 0, 0}, {0, 0, -1, 0, 0, 1, 0}, {0, 0, 0, -1, 0, 0, 1}, {A, 0, 
    1, A/B, 0, 0, 0}, {B, 0, B/A, 1, 0, 0, 0}};

Dimensions@matrix
MatrixForm@matrix

{7, 7}

For the reader's convenience, the task at hand is to compute the determinant of the initial/seed matrix and all submatrices. Hence, we need to compute ALL SQUARE submatrices.

• Step 1: Computing the determinant of the seed matrix just to get it out of the way:

  Det@matrix

0

• Step 2: Previously, I suggested Subsets, but upon reflection I think that the way to go about it is Minors.

For the seed $7 \times 7$ matrix we run

obo = Minors[matrix, 1, Identity];
tbt = Minors[matrix, 2, Identity];
ttbtt = Minors[matrix, 3, Identity];
fbf = Minors[matrix, 4, Identity];
ffbff = Minors[matrix, 5, Identity];
sbs = Minors[matrix, 6, Identity];

To obtain all the sub-ones. The outputs are large, however, for display purposes one can try for instance

Grid@Partition[MatrixForm /@ sbs[[1]], 5]

and for sbs[[2]] etc up until sbs[[Length@sbs]]. The output of the above looks as follows:

Thus, we have obtained all $1 \times 1$, $2 \times 2$, etc.

• Step 3: computing their determinants.

A demonstration for the $1 \times 1$ cases.

obo

returns

{{{{1}}, {{1}}, {{1}}, {{1}}, {{0}}, {{0}}, {{0}}}, {{{1}}, {{0}}, \ {{0}}, {{0}}, {{1}}, {{1}}, {{1}}}, {{{0}}, {{-1}}, {{0}}, {{0}}, \ {{1}}, {{0}}, {{0}}}, {{{0}}, {{0}}, {{-1}}, {{0}}, {{0}}, {{1}}, \ {{0}}}, {{{0}}, {{0}}, {{0}}, {{-1}}, {{0}}, {{0}}, {{1}}}, {{{A}}, \ {{0}}, {{1}}, {{A/B}}, {{0}}, {{0}}, {{0}}}, {{{B}}, {{0}}, {{B/ A}}, {{1}}, {{0}}, {{0}}, {{0}}}}

and we can calculate and display the determinants as follows:

Grid@Partition[Table[Det /@ obo[[i]], {i, 1, Length@obo}], 4]

The $2 \times 2$ cases

Grid@Partition[Table[Det /@ tbt[[i]], {i, 1, Length@tbt}], 4]

Answer 2

As far as I can see with Mathematica the original matrix A must be tall and thin for your setup to work. If you have a short and fat matrix B as the original - take its transpose C = Transpose[B] (since if B is TUM its transpose is also TUM). Then apply the steps to validate TUM property.