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