# How to prove the symmetric Pascal matrix has all positive minors (totally positive)?

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