Is a TU matrix appended with smaller identity matrices still TU?

50 Views Asked by At

Let $A$ be a TU matrix of consecutive ones, and $I$ be an identity matrix. We know a TU matrix appended to an identity matrix, e.g., $$\begin{bmatrix} & & & | & & & \\ & A & & | & I & &\\ & & & | & & &\\ \end{bmatrix}$$ remains to be TU.

Then, can I further append smaller identity matrices, e.g., $$\begin{bmatrix} & & & | & & & | I\\ & A & & | & I & & | I\\ & & & | & & & | I\\ \end{bmatrix}$$ and keep TU structure?

1

There are 1 best solutions below

0
On

Consider the consecutive-ones matrix $$A=\begin{pmatrix} 1&0&0&0\\ 0&0&0&0\\ 0&1&0&0\\ 1&1&0&0 \end{pmatrix};$$ from the matrix $$\begin{pmatrix} A&\Biggm|&I_4&\Biggm|&\begin{matrix}I_2\\I_2\end{matrix} \end{pmatrix}$$ we take the first two and last two columns to obtain the submatrix $$\begin{pmatrix} 1&0&1&0\\ 0&0&0&1\\ 0&1&1&0\\ 1&1&0&1 \end{pmatrix},$$ which has determinant $-2$.