Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 2

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} $$

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.