# Writing matrices deduced from upper triangular 0-1 matrices as a product of a permutation matrix and an upper triangular matrix

Let $$C$$ be an upper triangular matrix with entries 0 or 1 such that every diagonal entry is equal to one. Let $$M_C:=-C^{-1}C^T$$.

Question: Is there a nice direct criterion (or even classification) on $$C$$ such that we can write $$M_C= \pi U$$, where $$\pi$$ is a permutation matrix and $$U$$ is an upper triangular matrix?

Call $$C$$ matrix regular if we can write $$M_C= \pi U$$.

This basically means that in the PLU decomposition of $$M_C$$ we have that $$L$$ is the identity (see LU factorization with partial pivoting).

The question comes from a homological algebra problem and a nice solution might solve some classification problems. Maybe there is a nice answer to the above question in terms of linear algebra?

Here two examples for such matrices $$C$$ and related problems:

Example 1: Dyck paths

A Dyck path of length $$n$$ is a list of positive integers $$[c_1,c_2,\dotsc,c_n]$$ with $$c_i -1 \leq c_{i+1}$$ for all $$i$$ and $$c_i \geq 2$$ for $$i \neq n$$ and $$c_n=1$$. (One can show that those sequences really correspond to the classical Dyck paths via the area sequence and the number of Dyck paths of length $$n$$ is $$C_{n-1}$$ when $$C_n$$ denotes the Catalan numbers.) Dyck paths can get naturally identified with the Nakayama algebra $$A_D$$ with a linear quiver having Kupisch series $$[c_1,c_2,\dotsc,c_n]$$, see for example Marczinzik, Rubey, and Stump - A combinatorial classification of 2-regular simple modules for Nakayama algebras.

Let $$D=[c_1,c_2,\dotsc,c_n]$$ be a Dyck path of length $$n$$. We define the Cartan matrix $$C_D$$ of $$D$$ as the $$n \times n$$ upper triangular matrix with entries 0 or 1 as follows: In the $$i$$-th row $$C_D$$ has entries equal to one in position $$(i,i)$$, $$(i,i+1)$$, …, $$(i,i+c_i-1)$$ and all other entries are zero.

Question 2: What are the Dyck paths with matrix regular Cartan matrix?

For example for $$n=5$$ there are 14 Dyck paths:

[ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 3, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 2, 3, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 4, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 3, 4, 3, 2, 1 ], [ 4, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

and nine of them have matrix regular Cartan matrix:

[ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ].

(This question is related to a recent classification problem for Nakayama algebras, see for example Ringel - Linear Nakayama algebras which are higher Auslander algebras.)

Example 2: posets

Assume all posets are finite and bounded (meaning they have a global maximum and minimum). Then the Cartan matrix of a poset $$P$$ (or also called lequal matrix) is simply the matrix $$C$$ with entries $$C_{x,y}=1$$ if $$x \leq y$$ and $$C_{x,y}=0$$ else. Of course we can always assume that $$C$$ is upper triangular by reordering $$P$$.

Question 3: Is it true that a lattice $$L$$ is distributive if and only if the Cartan matrix of $$L$$ is matrix regular?

Hugh Thomas showed me a proof in a much more general setting that shows that being distributive implies that the Cartan matrix is matrix regular. In the case of a distributive lattice the permutation $$\pi$$ corresponds to the rowmotion bijection on the points of $$L$$.

Maybe this gives a useful example. Take $$C=[c_{i,j}]$$ an $$n\times n$$ matrix with $$\begin{cases}c_{i,i}=1,\forall i\\ c_{i,n-i+1}=1, i=1,\ldots,\lfloor \frac{n}{2} \rfloor\\ c_{i,j}=0 \text{ otherwise}\end{cases}$$
Let $$\pi=P=[p_{i,j}]$$ be the anti diagonal permutation matrix $$(p_{i,n-i+1}=1)$$.
The matrix $$PU=A=[a_{i,j}]$$ is defined as $$\begin{cases}a_{i,n-i+1}=1, i=1,\ldots,\lfloor \frac{n}{2} \rfloor \\a_{i,i}=a_{i,n-i+1}=-1; i=\lceil \frac{n}{2} \rceil,\ldots,n\\ a_{i,j}=0 \text{ otherwise}\end{cases}$$ It can be verified that $$CPU = -C^T$$ with $$PA=U$$ an upper triangular matrix.