# inverse of a binomial matrix

I have a matrix $A$ ($n \times n$) defined as follows:

$$A = \{ 0 \text{ if } i<j,\ \mathrm{Binom}(x=i, \mathrm{size}=j, \mathrm{prob})\text{ if } j \ge i\}$$

This is an upper triangular matrix, and I want to solve a system $Ax =b$ -- thus in a sense invert $A$.

I was wondering if a general inverse exists for this problem.

Any help appreciated, thanks in advance..

-
So what you mean is that the $(i,j)$ entry is $\dbinom i j$? –  Michael Hardy Nov 12 '12 at 15:13
@MichaelHardy \choose(j,i) prob^{i} *(1-prob)^{j-i} –  Roark Nov 12 '12 at 20:09
You're using computer code instead of mathematical notation. You can write $\dbinom j i p^i (1-p)^{j-i}$. –  Michael Hardy Nov 12 '12 at 23:10

## 2 Answers

Let $q=1-p$ and $r = \frac pq$. Then $$A_{ij} = \begin{cases}{j\choose i} r^i q^j, & i\le j,\\0 & i>j.\end{cases}$$ Therefore $A = \mathrm{diag}(r,r^2,\ldots,r^n)\ B\,\ \mathrm{diag}(q,q^2,\ldots,q^n)$ where $$B_{ij} = \begin{cases}{j\choose i}, & i\le j,\\0 & i>j.\end{cases}$$ The matrix $B$ is intimately related to the definition of Pascal matrix. The entries of $C=B^{-1}$ are known to take the following form: $$C_{ij} = \begin{cases}{j\choose i} (-1)^{i+j}, & i\le j,\\0 & i>j.\end{cases}$$ Hence the entries of the $M=A^{-1}$ are given by $$M_{ij} = \begin{cases}{j\choose i} (-1)^{i+j} q^{-i}r^{-j}, & i\le j,\\0 & i>j.\end{cases}$$

-
Thank you very much, I just figured that out myself as well. Still, I really appreciate your answer. –  Roark Nov 13 '12 at 22:55

I suspect it is a lower triangular matrix. Anyway, append it with an identity matrix and start eliminating from bottom to top (top to bottom). See Gauss-Jordan elimination.

-
it is actually upper-triangular the way I defined it. I know how to solve the problem with elimination and backsubstition. The issue is when I do so, some of the x variables exceed double max-min limits thus can not be computed. For that reason, I am investigating whether a nice form of inv(A) exists –  Roark Nov 12 '12 at 15:22
@Roark In your definition, both of inequalities are of $j \ge i$ form. Is it a typo? –  Dilawar Nov 12 '12 at 16:02
No, it's not. The diagonal entries are then prob^{i} –  Roark Nov 12 '12 at 20:10