In my study of matrix theory I came across this problem on which I am stuck:

The symmetric Pascal matrix $ P(n) $ is an $ n \times n $ real symmetric matrix defined by the following recurrence relation $ p_{1i}=p_{i1}=1 $ for every $ 1 \leq i \leq n $ and $ p_{ij}=p_{i-1,j}+p_{i,j-1} $ for $ 2 \leq i,j \leq n $ We are asked to prove $ P(n) $ is totally positive (all of its minors are positive).

As a hint, we are asked to find a non singular totally non-negative triangular matrix S (a non singular square triangular matrix with all non-negative minors) such that we have the equality $ P(n+1) = S(1 \oplus P(n))S^T $ where $ \oplus $ denotes direct sum of matrices (defining a block diagonal matrix).

My problem is I cannot find such a matrix $ S $ and moreover I don't understand how the equality in the hint can be used to prove $ P(n+1) $ is totally positive, I thought about induction on $ n $ but $ S $ is only totally non-negative and I know the product of totally positive matrices is totally positive, so how would this hint prove to be useful in proving all minors of $ P(n+1)=S(1 \oplus P(n))S^T $ are positive? I appreciate all help.


This will not use your hint, but it is an answer anyway.

Your matrix has $p_{i,j} = \dbinom{\left(i-1\right) + \left(j-1\right)}{i-1}$ for all $i$ and $j$ (because the $p_{i,j}$ satisfy the same recursion as the binomial coefficients $\dbinom{\left(i-1\right) + \left(j-1\right)}{i-1}$, with the same starting values $p_{1,j}$ and $p_{i,1}$). So the minors of this matrix have the form $\det\left(\left(\dbinom{a_i+b_j}{a_i}\right)_{1\leq i\leq k, \ 1 \leq j\leq k}\right)$, where $k$ is a nonnegative integer, where $\left(a_1 < a_2 < \cdots < a_k\right)$ is a strictly increasing $k$-tuple of nonnegative integers, and where $\left(b_1 < b_2 < \cdots < b_k\right)$ is a further strictly increasing $k$-tuple of nonnegative integers. So you have to prove that such determinants are positive.

Consider the (infinite) directed graph $\Pi$ whose vertices are pairs of integers, and whose arcs are $\left(i,j\right) \to \left(i+1,j\right)$ (the "horizontal arcs") and $\left(i,j\right) \to \left(i,j-1\right)$ (the "vertical arcs") for all $\left(i, j\right) \in \mathbb{Z}^2$. A lattice path will mean a directed path on this graph $\Pi$. Then, $\det\left(\left(\dbinom{a_i+b_j}{a_i}\right)_{1\leq i\leq k, \ 1 \leq j\leq k}\right)$ is the number of $k$-tuples $\left(w_1, w_2, \ldots, w_k\right)$ of lattice paths satisfying the following two conditions:

(1) For each $i$, the lattice path $w_i$ starts at $\left(a_i, 0\right)$ and ends at $\left(0, b_i\right)$.

(2) The paths $w_1, w_2, \ldots, w_k$ are pairwise vertex-disjoint (i.e., have no vertex in common).

This fact is a straightforward consequence of the Lindström-Gessel-Viennot lemma (since the digraph $\Pi$ is planar); if you do not know this lemma, you can read up a proof of a very similar fact in Ira Gessel, Gérard Viennot, Binomial Determinants, Paths, and Hook Length Formulae, Advances in Mathematics, Volume 58, Issue 3, December 1985, Pages 300--321 (it is Theorem 1 in there).

So we know that the determinant $\det\left(\left(\dbinom{a_i+b_j}{a_i}\right)_{1\leq i\leq k, \ 1 \leq j\leq k}\right)$ counts certain $k$-tuples. In order to show that this determinant is positive, we thus only need to check that there exists such a $k$-tuple. But this is easy: For each $i$, let $w_i$ be the lattice path from $\left(a_i, 0\right)$ to $\left(0, b_i\right)$ that is obtained by first walking along horizontal arcs up until $\left(a_i, b_i\right)$, and then continuing along vertical arcs until $\left(0, b_i\right)$. Thus, we obtain a $k$-tuple $\left(w_1, w_2, \ldots, w_k\right)$ which satisfies conditions (1) and (2) above (this is easily seen).


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.