# Inverting the infinite matrix $+\mathbf{I}$ with entries $\mathbf{P}_{ij}={i-1\choose j-1}$ [closed]

Let $\mathbf{P}$ denote the "infinite matrix"

$$\left[ \begin{array}{ccccc} 1 & 0 & 0 & 0 & \dots \\ 1 & 1 & 0 & 0 & \dots \\ 1 & 2 & 1 & 0 & \dots \\ 1 & 3 & 3 & 1 & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array} \right]$$

with entries $\mathbf{P}_{ij} = \dbinom{i-1}{j-1}$ and let $\mathbf{I}$ denote the "infinite identity matrix." Compute the inverse of $\mathbf{P} + \mathbf{I}$.

This was not the initial attempt. I couldn't think of anything at first. But after some nudges, I tried to compute the $n\times n$ matrix $\mathbf{P}_n$. Now my first observation was $\det \mathbf{P}_n=1$. Now if I could show that the invertibility of $\mathbf{P}_n$ would be efficient. So we expand $\mathbf{P}_{n+1}$ by the last row, then it is obvious that $\det \mathbf{P}_{n+1}=\det \mathbf{P}_n=1$. So invertibility is meaningful. But when I inverted for small values, I couldn't find any pattern. I can't think of a method to cook up the solution. Can someone help me? I see my method of thinking should have been presented and I apologise. I will add them later on.

How to compute an inverse of an infinite matrix? And even if I can, what to do with it? Thanks for any help.

## closed as off-topic by heropup, colormegone, Najib Idrissi, Claude Leibovici, Jean-Claude ArbautAug 24 '14 at 9:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – heropup, colormegone, Najib Idrissi, Claude Leibovici, Jean-Claude Arbaut
If this question can be reworded to fit the rules in the help center, please edit the question.

• Why do you want to compute the inverse? Who told you there is something you can do with it? – Jonas Meyer Aug 21 '14 at 15:12
• My teacher gave me this problem. He said he has done it. I hope this satisfies your queries? @JonasMeyer Thanks. Now could you help me out here? Thanks again. – shadow10 Aug 21 '14 at 15:16
• It's possible the teacher just wants you to discover some pattern in the inverse, then prove that this pattern holds for the whole matrix. It looks like this matrix contains Pascal's triangle, although I don't know for sure. – rschwieb Aug 21 '14 at 15:16
• It looks like $P_{ij}^{-1}=(-1)^{i+j}P_{ij}$. – g.kov Aug 21 '14 at 19:32
• @shadow10 It seems like there was a rather obvious pattern emerging right at the start, which I think is what g.kov was mentioning. Did it break down on some row? As I mentioned, there's no point in talking about determinants for an infinite matrix. If you find a formula for the entries of the inverse, then you can just check the matrix multiplication directly to see if it is something like the Kronecker delta function. – rschwieb Aug 22 '14 at 12:29

## 2 Answers

For now, let's focus on inverting $\mathbf{P}$. (The method below should work for $\mathbf{I}+\mathbf{P}$ as well but I didn't want to start there). First, note that the elements of $\mathbf{P}^{-1}$ satisfy $$(\mathbf{P}\cdot\mathbf{P}^{-1})_{ik}=\sum_{j} \mathbf{P}_{ij}(\mathbf{P}^{-1})_{jk} =\sum_j \binom{i-1}{j-1}(\mathbf{P}^{-1})_{jk}=\delta_{ik}.$$ Note that this is still a linear algebra problem, albeit with an infinite number of variables and constraints.

I'll attack it with a generating function approach: Multiplying the LHS by $x^i$ and summing over all integers produces

\begin{align} \sum_{ij} \binom{i-1}{j-1}(\mathbf{P}^{-1})_{jk}x^i=\sum_j (\mathbf{P}^{-1})_{jk}\sum_i\binom{i-1}{j-1}x^i = \sum_{j=1}^\infty (\mathbf{P}^{-1})_{jk}\left(\frac{x}{1-x}\right)^j. \end{align} To justify the last equality, shift the index of summation of $i\mapsto i+j$: $$\sum_i\binom{i+j-1}{j-1}x^{i+j}=x^j\cdot \sum_i\binom{i+j-1}{i}x^{i}=\dfrac{x^j}{(1-x)^j}$$ since the last summation is a (negative) binomial series. If we repeat this on the RHS we simply get $x^k$ since the Kronecker delta kills the rest of the terms. We then let $y=\dfrac{x}{1-x}$ and equate the RHS and LHS to obtain

$$\sum_{j=1}^\infty (\mathbf{P}^{-1})_{jk}y^k =\left(\frac{y}{1+y}\right)^k=(-1)^k\left[\frac{(-y)}{1-(-y)}\right]^k=(-1)^k\cdot \sum_j\binom{j-1}{k-1}(-y)^j$$ with the last equality following from the prior equation. Identifying coefficients on both sides then finally gives $\boxed{(\mathbf{P}^{-1})_{jk}=(-1)^{j+k} \binom{j-1}{k-1}}$. Comparing with our original equation, this implies the summation $\sum_j (-1)^{j+k} \binom{i-1}{j-1}\binom{j-1}{k-1}=\delta_{ik}$; this almost certainly admits a counting proof via inclusion-exclusion.

So we may take $\mathbf{P}^{-1}$ as known, and can now focus on $(\mathbf{I}+\mathbf{P})^{-1}$. Something like the binomial inverse theorem should come in handy; I'll see if I can find a simple route.

Let $V$ be the vector space of polynomials (or polynomial functions if you prefer that). Let us look at the transpose of $P$ instead of $P$. We see immediately that $P^T$ is the matrix of the linear transformation $S:p(x)\mapsto p(x+1)\in GL(V)$ with respect to the natural basis $\{1,x,x^2,\ldots\}$. Therefore the inverse of $P^T$ is the transpose of the matrix of the inverse transformation $S^{-1}:p(x)\mapsto p(x-1)$. This proves the observation/conjecture in a comment by g.kov: $P^{-1}_{ij}=(-1)^{i+j}P_{ij}$.

The matrix $I+P^T$ corresponds to the transformation \begin{aligned} R:p(x)\mapsto & p(x)+p(x+1)\\ =&p(x)+p(x)+Dp(x)+\frac{D^2}2p(x)+\cdots\\ =&(1+e^D)p(x). \end{aligned} Therefore its inverse is $$R^{-1}=\frac1{1+e^D}=\frac12+\frac12\cdot\frac{1-e^D}{1+e^D}=\frac12(1+\tanh\frac D2).$$ The Taylor series of the hyperbolic tangent is too scary for me, so may be I stop.

• You might find the two links I posted above in comments earlier interesting for comparison with that last result. (I'll admit, once I saw those two papers I gave up on there being a simple approach.) – Semiclassical Aug 24 '14 at 23:41
• @Semiclassical: Thanks. I did miss those links. My main point was to give a simple argument for $P^{-1}$. – Jyrki Lahtonen Aug 25 '14 at 4:24
• The series begins with $1/2 + 1/4 D - 1/48 D^3 + 1/480 D^5 - 17/80640 D^7 + 31/1451520 D^9$ $- 691/319334400 D^{11} +...$. The numbers $17,31,691$ in connection with the index in steps of 2 should ring some bell in direction of Bernoulli-numbers, or even better, of Euler numbers (see wikipedia). The remaining seems to be not too difficult... – Gottfried Helms Sep 27 '14 at 1:24