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

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.

• What about Minors[matrix, 4, Det]? Commented Mar 23, 2022 at 4:25
• Would that calculate all possible determinants of matrix 4x4? Commented Mar 23, 2022 at 15:24
• Much easier if you work mod 3. Just saying. Commented Mar 23, 2022 at 23:19
• Could you elaborate? please Commented Mar 24, 2022 at 14:54
• It was intended in jest. Mod 3 all minors are 0, 1 or -1. Commented Mar 28, 2022 at 18:33

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

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]


• I try it with an example I had done by hand and its exactly what I wanted!! Thank you so much for being so detailed in the steps!! I learn a lot!! Commented Mar 22, 2022 at 21:50
• @orpanter glad to hear that there are no mistakes. in my response. Good luck with your studies/projects and please do consider accepting the answer :-)
– bmf
Commented Mar 22, 2022 at 21:52
• I will! But one quick question before, if the output is only {0}, it means that all solutions from where the same and equal to 0? Commented Mar 23, 2022 at 15:24
• I use it for this 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}} Commented Mar 23, 2022 at 15:37
• @orpanter many thanks for the feedback and for providing the explicit matrix. I will make sure to have a look a bit later. Just a quick comment. The output {0} is informing you that you obtained a list, with one element precisely, that is equal to 0.
– bmf
Commented Mar 23, 2022 at 15:57

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.