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

Question

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$.

Answer 1

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.