5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think there's a typo in your matrix, which has determinant 0. The bottom row should be 2 1 1 rather than 1 1 1; the resulting matrix has determinant 1. $\endgroup$ Aug 1, 2020 at 14:12

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Consider the simple case, where $\lambda$ has n rows of length n. Namely, $M$ covers all the boxes of $\lambda$. It is easy to prove $M_{i,j}=\binom{2n-i-j}{n-j}$, but how can you prove $det(M)=1$? Can it be shown using Gessel-Viennot Theorem? $\endgroup$
    – Ido
    Jun 20, 2020 at 8:11
  • $\begingroup$ @Ido Letting $M_n$ be that matrix when lambada is an $n×n$ square, you can use row operations to reduce $M_n$ so that it’s upper left $(n-1)×(n-1)$ submatrix is $M_{n-1}$, the proceed by induction. $\endgroup$ Jun 20, 2020 at 18:00
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.