Given a Ferrers diagram, prove that $\det(M)=1$

Question

Let $\lambda$ be a Ferrers diagram corresponding to some integer partition of $k$. We number the rows and the columns, so that the j'th leftmost box in the i'th upmost row is denoted as $(i,j)$. Let $n$ be the largest number, such that the box $(n,n)$ is part of the diagram.

For each box $(i,j)\in \{1,\dots,n\}^2$ let $\ell(i,j)$ be the lowest box in the $j$'th column of $\lambda$, and let $r(i,j)$ be the rightmost box in the $i$'th row of $\lambda$. Note that $\ell(i,j)$ and/or $r(i,j)$ might be $(i,j)$ itself.

We think about the diagram as a grid of vertices, such that the $(i,j)$ vertex is connected to $(i-1,j)$ and $(i,j+1)$ with directed edges. We define $M\in \mathbb{R}^{n\times n}$ such that $M_{i,j}$ is the number of directed paths from $\ell(i,j)$ to $r(i,j)$. Namely, the number of "walks" in which every step is either one move upward or one move to the right. Note that we thus get a square matrix with positive integer entries.

Prove that for any $\lambda$ we have $\det(M)=1$.

Here is an example of a Ferrers diagram $\lambda$ in which $M$ is $3\times3$, along with the corresponding numbers $M_{i,j}$ we put in each box $(i,j) \in \{1,\dots,n\}^2$ as defined above.

$ \begin{align} 9&&3&&1&&☐ \\ 5&&2&&1&& \\ 1&&1&&1&& \\ ☐&&☐&&&& \\ ☐&&&&&& \\ \end{align} $ (See: https://i.stack.imgur.com/9RaP4.png)

I tried to prove it using induction. I tried to show that if you make the following row operation, you eventually get a triangular matrix with 1's on the diagonal. $$ \textrm{for $i=n,n-1,\dots,1$ do:}\\ \textrm{for $k=i-1,i,\dots,1$ do:}\\ R_{k} \longleftarrow R_{k}-M_{k,i}\cdot R_{i} $$ But it didn't go well.

Answer 1

Here is an observation, which I think gives helpful progress towards a solution. Consider how the matrix for $\lambda$ relates to the matrix for $\lambda'$, where $\lambda'$ is obtained by removing a corner square of $\lambda$ which is not in $M$.

In your example, if you remove the lowest square of the Ferrer's diagram, then it turns out none of the numbers change. More interestingly, consider removing the rightmost square in the second row from the bottom, and computing the new matrix $M'$. The result is

6 3 1 ☐ ☐
3 2 1
1 1 1
☐
☐

Now, how does this new matrix $M'$ relate to the old matrix $M$? Note the $M$' can be obtained from $M$ by a single elementary column operation, namely, subtracting the second column in $M$ from the first. In general, $M'$ will be obtained by $M$ by several row or column operations. Essentially, this is because deleting a box from $\lambda$ removes certain paths, all of which corresponded to paths in a different column. Since these column operations do not change the determinant, $\det M=\det M'$, allowing you to conclude $\det M=1$ by induction on the number of boxes in $\lambda$.

You might have to adjust this argument a little bit when $\lambda$ is a square, so that there are no boxes outside of $M$ to remove, but here you can probably directly prove $\det M=1$, since there is a simple formula for the entries of $M$.

Answer 2

I believe your problem is solved by a direct application of the Gessel-Viennot lemma. Also, one bit of terminology: The box $\{1, \ldots, n\}^2$ that you describe is known as the Durfee square of a partition.

Using your up & right directions, you can make the Young diagram a directed acyclic graph, so Geseel-Viennot applies. The $M_{ij}$ entry records paths from $\ell(i,j)$ to $r(i,j)$, i.e., from the bottom of the $j$th column to the rightmost box of the $i$th row. As an aside, the permanent of $M$ gives the number of $n$-tuples of paths from the collection of bottom boxes to the collection of rightmost boxes.

The determinant of $M$ gives the number of nonintersecting $n$-tuples of paths from the collection of bottom boxes to the collection of rightmost boxes. But there's only one such $n$-tuple: the hooks down the diagonal of the Durfee square. That is, the paths from the bottom of each $i$th column up to the position $(i,i)$ box and right to the end of the $i$th row. So $\det(M)=1$.

(To me, using the matrix entries as labels of boxes in the Durfee square of the Young diagram is a little bit of a red herring. Looking at the figure, I wonder about the unfilled boxes. The size of the Durfee square matters because there is only "room" for $n$ nonintersecting paths from sources below the diagonal to sinks right of the diagonal.)