Multiply row and columns of a totally unimodular matrix – is the result still totally unimodular.

discrete mathematicsdiscrete optimizationinteger programmingoptimizationtotal-unimodularity

given a totally unimodular matrix $A$, i.e. a matrix where each subdeterminant is either $+1, -1$ or $0$. Now we multiply some rows and columns of $A$ with $(-1)$ to get a matrix $B$. Is the following statement true: $A$ is totally unimodular iff $B$ is totally unimodular.

I am tempted to say the answer is "yes" since multiplying rows and columns with $(-1)$ will only switch the sign of the determinant.

Is this correct?

Best Answer

Let $\hat{A}$ be the altered matrix. We can write it as $\hat{A} = D A \bar{D}$ where $D$ and $\bar{D}$ are diagonal matrices all diagonal entries $\pm 1$. $D_{ii}=-1$ if row $i$ of $A$ is being negated and $\bar{D}_{ii}=-1$ if column $i$ of $A$ is being negated.

Any square submatrix of $\hat{A}$ is the product of a diagonal submatrix of $D,$ the same square submatrix of $A,$ and a diagonal submatrix of $\bar{D}.$ The submatrices of $D$ and $\bar{D}$ have determinant $\pm 1,$ the submatrix of $A$ has determinant in $\lbrace -1, 0, 1\rbrace,$ and the determinant of a matrix product is the product of the determinants.

So the answer is yes.