13
$\begingroup$

Let $P_n$ be the $(n+1) \times (n+1)$ matrix that contains the numbers of Pascal's triangle in the upper triangle. For example in the case of $n=3$ $$ P_3 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} $$ or in general $$ (P_n)_{ij} = \binom{j}{i} \lfloor i \leq j \rceil ~~~\text{for}~~ i,j \in \{0,...,n \} $$ using the definition $$ \lfloor A \rceil := \begin{cases} 1 & \text{A is true} \\ 0 & \text{A is not true} \end{cases} $$ This matrix is invertible since $\det P_n = 1$. For smaller cases like $n=3$, I calulated the inverse of the matrix by hand and found $$ P_3^{-1} = \begin{pmatrix} 1 & -1 & 1 & -1 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 1 & -3 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} $$ $n=2,4$ led to similar results, so I'm guessing that the inverse should be $$ (P_n^{-1})_{ij} = (-1)^{j+i}(P_n)_{ij} = (-1)^{j+i} \binom{j}{i} \lfloor i \leq j \rceil $$ But I have not been able to prove or disprove this yet. So far I tried multiplying the two matirces which gives $$ \sum^j_{k=i} (-1)^{j+k} \binom{j}{k} \binom{k}{i} = \delta_{ij} $$ if one asumes that the result is the unit matrix. For $i=0$ and $j>0$ this gives $$ \delta_{0j} = 0 = \sum^j_{k=0} (-1)^{j+k} \binom{j}{k} \binom{k}{0} = \sum^j_{k=0} (-1)^{k} \binom{j}{k} $$ which is an identity I know to be true, so it reasures me a little bit that the above should also be true.

$\endgroup$
3
  • $\begingroup$ Instead of proving the above mentioned formula for all $(j,i)$ you can also use induction and prove it only for $(n,i)$, maybe it is easier. The $(j,n)$ entries are easy to handle $\endgroup$
    – b00n heT
    Jul 8, 2016 at 6:23
  • 4
    $\begingroup$ Use $\binom jk \binom ki = \binom ji \binom {j-i}{k-i}$. $\endgroup$ Jul 8, 2016 at 6:36
  • 1
    $\begingroup$ Binomial transform $\endgroup$ Jul 27, 2016 at 11:10

4 Answers 4

10
$\begingroup$

In my opinion this is a bit simpler to prove, if we interpret the matrix $P_n$ as a linear transformation.

Consider the space $V_n$ of polynomials of degree $\le n$ (over, say $\Bbb{Q}$, but you are welcome to use reals or complex numbers, or any other field actually).

The mapping $T: f(x)\mapsto f(x+1)$ for all $f(x)\in V_n$ is obviously linear. My key point is to observe that $P_n$ is the matrix $M_{\mathcal B}(T)$ of $T$ with respect to the obvious basis $\mathcal{B}=\{1,x,x^2,\ldots,x^n\}$ of $V_n$. This is because for any $k, 0\le k\le n$ the binomial formula says that $$T(x^k)=\sum_{\ell=0}^k\binom k\ell x^\ell.$$ From this we can read the coordinates of $T(x^k)$ with respect to $\mathcal{B}$, and see that those coincide the $k$th column of $P_n$ (numbered from $0$ to $n$). That's exactly what the claim was.

It is obvious that the inverse of $T$ is given by the recipe $ T^{-1}:f(x)\mapsto f(x-1). $ A similar application of the binomial formula shows that the matrix $M_{\mathcal B}(T^{-1})$ then is exactly your prescribed inverse of $P_n$ containing binomial coefficients - this time with alternating signs.

But, by basic linear algebra $$ M_{\mathcal B}(T^{-1})=M_{\mathcal B}(T)^{-1}. $$

$\endgroup$
2
  • 1
    $\begingroup$ Nice solution! I especially like that it does not require to guess the form of the inverse. It is also very close to the reason I got confronted with the problem in the first place. Because I was looking at the change of base from $\{x^j\}$ to $\{(x+1)^j\}$. $\endgroup$
    – Léreau
    Jul 22, 2016 at 18:39
  • 2
    $\begingroup$ @JyrkiLahtonen This is brilliant, really, a pity that I can only give (+1). I just wanted to know the formula for the inverse of the Pascal matrix and searched the web for it. Now I found not only the formula, but this higher level view on it which makes everything so clear. It feels similar to the moment when I was told that the addition theorems for sin and cos are just real and imaginary parts of the power rule for the complex exponential function. $\endgroup$
    – azimut
    May 30, 2020 at 10:10
8
$\begingroup$

By the suggestion of Sungjin Kim one can use \begin{equation} \binom{j}{k}\binom{k}{i} = \binom{j}{i}\binom{j-i}{k-i} \end{equation} which is useful since it leads to the sum only going over one of the binomial coefficients. It leads to \begin{align} \sum^j_{k=i} (-1)^{j+k} \binom{j}{k} \binom{k}{i} &= \sum^j_{k=i} (-1)^{j+k} \binom{j}{i}\binom{j-i}{k-i} \\ &= (-1)^j \binom{j}{i} \sum^j_{k=i} (-1)^{k} \binom{j-i}{k-i} \\ &= (-1)^{j} \binom{j}{i} \sum^{j-i}_{k=0} (-1)^{k+i} \binom{j-i}{k} \\ &= (-1)^{j+i} \binom{j}{i} (1 - 1)^{j-i} = \delta_{ij} \end{align} The identity used is easily proven by $$ \binom{j}{k}\binom{k}{i} = \frac{j!}{k!(j-k)!} \frac{k!}{i!(k-i)!} = \frac{j!}{i!(j-i)!} \frac{(j-i)!}{(j-k)!(k-i)!} = \binom{j}{i}\binom{j-i}{k-i} $$ Another way of showing the identity involving $\delta_{ij}$ is to start with $x^j$ and using the binomial thoerem twice $$ x^j = (x+0)^j = ((x+1) - 1 )^j = ~...~ = \sum^j_{i=0} \sum^j_{k=i} (-1)^{j+k} \binom{j}{k} \binom{k}{i} x^i $$ comparing coefficients of the two sides of the equation, then also leads to the desired result. You can find the whole calcultion here, along whith other examples of when adding 0 really counts.

$\endgroup$
4
$\begingroup$

In the following it's somewhat more convenient to equivalently consider the transpose $P_n^T$ of the matrix $P_n$ and its inverse.

We obtain for $n=3$

\begin{align*} P_3^T&= \begin{pmatrix} 1 & & & \\ 1 & 1 & & \\ 1 & 2 & 1 & \\ 1 & 3 & 3 & 1 \\ \end{pmatrix}=\left(\binom{i}{j}\right)_{0\leq i,j\leq 3} \\ \left(P_3^T\right)^{-1}&= \begin{pmatrix} \begin{array}{rrrr} 1 & & & \\ -1 & 1 & & \\ 1 & -2 & 1 & \\ -1 & 3 & 3 & 1 \\ \end{array} \end{pmatrix}=\left((-1)^{i+j}\binom{i}{j}\right)_{0\leq i,j\leq 3} \end{align*}

The elements of the Pascal matrix can be considered as coefficients of binomial inverse pairs. These are sequences $(a_i)_{0\leq i \leq n},(b_i)_{0\leq i\leq n}$ which are related for $n\geq 0$ via \begin{align*} a_n=\sum_{i=0}^n\binom{n}{i}b_i\qquad\text{resp.}\qquad b_n=\sum_{i=0}^n(-1)^{i+n}\binom{n}{i}a_i\tag{1} \end{align*}

One relation implies the other in (1). This can be seen via exponential generating functions.

Let $A(x)$ and $B(x)$ be two exponential generating functions

$$A(x)=\sum_{n=0}^\infty a_{n}\frac{x^n}{n!} \qquad\qquad\text{ and }\qquad\qquad B(x)=\sum_{n=0}^\infty b_{n}\frac{x^n}{n!}$$

The expressions in (1) are the coefficients of

\begin{align*} A(x)=B(x)e^x\qquad\qquad\text{resp.}\qquad\qquad B(x)=A(x)e^{-x}\tag{2} \end{align*} The relationship in (2) is obvious and so the relationship in (1) follows.

The most important characterization of the pair of inverse relation in (1) is the orthogonal relation the pair implies. This follows by substituting one of the pair into the other. We obtain for $n\geq 0$

\begin{align*} a_n&=\sum_{j=0}^n\binom{n}{j}b_j\\ &=\sum_{j=0}^n\binom{n}{j}\sum_{i=0}^j(-1)^{i+j}\binom{j}{i}a_i\\ &=\sum_{i=0}^n a_i\sum_{j=i}^n(-1)^{i+j}\binom{n}{j}\binom{j}{i} \end{align*} Hence the orthogonal relation is \begin{align*} \delta_{ni}=\sum_{j=i}^n(-1)^{i+j}\binom{n}{j}\binom{j}{i} \end{align*} with $\delta_{ni}$ the Kronecker Delta.

$\endgroup$
0
$\begingroup$

The inverse of $P_n$ also follows from a familiar representation of $GL(2,\mathbb{R})$. Let $\{u,v\}$ be a basis of $\mathbb{R}^2$ and $S^n(\mathbb{R}^2)$ denote the vector space of homogeneous polynomials of degree $n$ in the variables $u$ and $v$. Then, any $A\in GL(2,\mathbb{R})$ acts linearly on $p(u,v)\in S^n(\mathbb{R}^2)$ by $A\cdot p(u,v)=p(Au,Av).$ Choose $\{u^{n-j}v^j\}_{j=0}^n$ as a basis of $S^n(\mathbb{R}^2)$. Then, the given group action induces a homomorphism $\varphi_n: GL(2,\mathbb{C})\to GL(n+1,\mathbb{C})$ defined by $$\begin{pmatrix}a & b\\ c & d\end{pmatrix}\mapsto \left([t^i](a+ct)^{n-j}(b+dt)^j\right)_{i,j=0}^n$$ where $[t^i]f(t)$ denotes the coefficient of $t^i$ in $f(t)$. Let $M=\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}.$ Then, we see that $P_n=\varphi_n(M).$ Since $\varphi_n$ is a homomorphism, we get $P_n^{-1}=\varphi_n(M^{-1})$. But $M^{-1}=\begin{pmatrix}1 & -1\\ 0 & 1\end{pmatrix}$. Hence, by definition of $\varphi_n$, we obtain explicit indices as you described.

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