2
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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}};

matrix

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}

7by7

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:

sbs[1]

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]

obodets

The $2 \times 2$ cases

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

tbtdets

$\endgroup$
8
  • $\begingroup$ 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!! $\endgroup$
    – orpanter
    Mar 22, 2022 at 21:50
  • 1
    $\begingroup$ @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 :-) $\endgroup$
    – bmf
    Mar 22, 2022 at 21:52
  • $\begingroup$ 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? $\endgroup$
    – orpanter
    Mar 23, 2022 at 15:24
  • $\begingroup$ 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}} $\endgroup$
    – orpanter
    Mar 23, 2022 at 15:37
  • $\begingroup$ @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. $\endgroup$
    – bmf
    Mar 23, 2022 at 15:57
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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