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 found a interesting thing but I cannot prove it. Given $k_i$ are positive for any $i\geq1$, and we have $M+1$ by $M+1$ matrix $A$, which is $$ A=\left[\begin{array}{ccccc} 0\\ k_{1} & 0\\ k_{2} & \frac{1}{2}k_{1} & 0\\ \vdots & & & \ddots\\ k_{M} & \frac{M-1}{M}k_{M-1} & \cdots & \frac{1}{M}k_{1} & 0 \end{array}\right] $$ I found that the first column of $n!A^{n}$ is always equal with the first column of $B^{n}$ for any $n\in\mathbb{N}$, where $$ B=\left[\begin{array}{ccccc} 0\\ k_{1} & 0\\ k_{2} & k_{1} & 0\\ \vdots & & & \ddots\\ k_{M} & k_{M-1} & \cdots & k_{1} & 0 \end{array}\right] $$ Can you help me to prove it? Thanks in advance.


The following is a reply to a comment from @GerryMyerson. (Updated on Aug. 27.)

To @GerryMyerson. Here is the problem when I use the induction:

Use induction method. First, it is obvious that when $n=0$ and $1$, the equality is hold for any $M\in\mathbb{N}$. Then, we assume when $n=N>1$, the equality is hold, and the matrix is $$ N!A_{M+1}^{N}=B_{M+1}^{N}=\left[\begin{array}{ccccccc} 0\\ \vdots\\ 0\\ t_{1} & 0\\ t_{2} & s & 0\\ \vdots & \vdots & & \ddots\\ t_{M+1-N} & u & \cdots & v & 0 & \cdots & 0 \end{array}\right]. $$ Here, we only focus on the first column.

When $n=N+1$, the left side is $$ \left(N+1\right)A_{M+1}\times\left(N!A_{M+1}^{N}\right)=\left(N+1\right)\left[\begin{array}{ccccccc} 0\\ k_{1} & 0\\ k_{2} & \frac{1}{2}k_{1} & 0\\ \vdots & & & \ddots\\ k_{i} & \frac{i-1}{i}k_{i-1} & \cdots & \frac{1}{i}k_{1} & 0\\ \vdots & & & & & \ddots\\ k_{M} & & & & & \frac{1}{M}k_{1} & 0 \end{array}\right]\left[\begin{array}{ccccccc} 0\\ \vdots\\ 0\\ t_{1} & 0\\ t_{2} & s & 0\\ \vdots & \vdots & & \ddots\\ t_{M+1-N} & u & \cdots & v & 0 & \cdots & 0 \end{array}\right], $$ then the $\left(i+1,1\right)$ entry is $\left(N+1\right)\left(\frac{i-N}{i}k_{i-n}t_{1}+\frac{i-N-1}{i}k_{i-N-1}t_{2}+\cdots+\frac{1}{i}k_{1}t_{i-N}\right)$.

On the other side, the $\left(i+1,1\right)$ of $B$ entry is $k_{i-N}t_{1}+k_{i-N-1}t_{2}+\cdots k_{1}t_{i-N}$.

Now, I cannot prove that these two are equal.

share|improve this question
    
Anyone helps? ::>_<:: –  Chang Aug 26 '12 at 14:42
1  
Any $n$ in $\bf R$? You're allowing real exponents? If you're happy with integer exponents, it looks like the kind of problem where induction is the thing to try. Have you tried it? –  Gerry Myerson Aug 27 '12 at 5:23
    
Oh~~sorry, $n$ is positive integer. Thanks. And I tried induction. Firstly I prove it is true when $n=1$, then I assume it is true when $n=N$, but when $n=N+1$, due to the lack of knowledge for the other columns, I cannot prove it.... –  Chang Aug 27 '12 at 8:46
1  
Hi Marc, thanks. However, the bottom left entry for $2!A^2$ is $2k_1k_2$, also it is the bottom left entry for $B^2$. They are the same. $$ \left[\begin{array}{cccc} 0\\ k_{1} & 0\\ k_{2} & k_{1} & 0\\ k_{3} & k_{2} & k_{1} & 0 \end{array}\right]^{2}=\left[\begin{array}{cccc} 0\\ 0 & 0\\ k_{1}^{2} & 0 & 0\\ 2k_{1}k_{2} & k_{1}^{2} & 0 & 0 \end{array}\right] $$ –  Chang Aug 27 '12 at 12:13
1  
You don't need to know anything about the other columns, do you? The first column of $A^{n+1}=AA^n$ depends on all the entries of $A$, but only on the first column of $A^n$. –  Gerry Myerson Aug 27 '12 at 12:29

1 Answer 1

up vote 9 down vote accepted

[Updated: it is now a proof of the property announced in the question. Somewhat surprisingly, in the end it boils down to an enumeration of permutations of a given cycle type.]

Here is an equivalent combinatorial formulation of the property you wish to prove. Let $\lambda=(\lambda_1\geq\cdots\geq\lambda_n)$ be a partition of some integer $i$ into $n$ nonzero parts. Let $p(\lambda)=\lambda_1\ldots\lambda_n$ be the product of the parts. Form the set $S$ of all multiset permutations of the parts (all distinct orderings of $\lambda_1,\ldots,\lambda_n$), of which there are $\#S=\frac{n!}{m_1(\lambda)!\,\ldots\,m_{\lambda_1}(\lambda)!}$, where $m_j(\lambda)$ is the multiplicity of $j$ as part of $\lambda$. For each sequence $(d_1,\ldots,d_n)\in S$ form the fraction $\frac1{d_1(d_1+d_2)\ldots(d_1+d_2+\cdots+d_n)}$, then the average value of those fractions over $S$ is $\frac1{p(\lambda)\,n!}$. Equivalently the sum of those fractions is $$ \frac1{p(\lambda)m_1(\lambda)!\,\ldots\,m_{\lambda_1}(\lambda)!} $$ which is the fraction of all permutations of $i$ whose cycle type is $\lambda$.

The explanation of the equivalence is straightforward computation of the expression for the entry $(A^n)_{i,0}$, where matrix rows and columns are counted from $0$. The contributions for a product $k_{\lambda_1}\ldots k_{\lambda_n}$ in this entry come from sequences $i>j_1>j_2>\cdots>j_{n-1}>0$ where $(i-j_1,j_1-j_2,\ldots,j_{n-2}-j_{n-1},j_{n-1}-0)$ is a permutation of the parts of $\lambda$. The coefficient attached to $k_{\lambda_1}\ldots k_{\lambda_n}$ in this contribution is $\frac{i-j_1}i\times\frac{j_1-j_2}{j_1}\times\cdots\times\frac{j_{n-1}-0}{j_{n-1}}$; the numerators always multiply out to $p(\lambda)$. For this to match, after multiplication by $n!$, the coefficient of $k_{\lambda_1}\ldots k_{\lambda_n}$ in the corresponding entry $(B^n)_{i,0}$, which entry is $\#S$, one needs the average value of $\frac{i-j_1}i\times\frac{j_1-j_2}{j_1}\times\cdots\times\frac{j_{n-1}-0}{j_{n-1}}$ to be $\frac1{n!}$, which is easily equivalent to what I wrote above.

So it will suffice to show that $$ \sum_{(d_1,\ldots,d_n)\in S}\frac{i!}{d_1(d_1+d_2)\ldots(d_1+d_2+\cdots+d_n)}=\#C_\lambda =\frac{i!}{p(\lambda)m_1(\lambda)!\,\ldots\,m_{\lambda_1}(\lambda)!}, $$ where $C_\lambda$ denotes the set of permutations of $i$ with cycle type $\lambda$. All factors in the denominator of the summand on the left can be cancelled in the numerator, so that the term is equal to the product of the remaining factors: $$ P(d_1,\ldots,d_n)=\prod \{\,j\mid 0<j<i\text{ and }j\notin\{d_1,d_1+d_2,\ldots,d_1+d_2+\cdots+d_{n-1}\}\,\}. $$ One can now prove the identity by partitioning $C_\lambda$ into parts of size $P(d_1,\ldots,d_n)$ for $(d_1,\ldots,d_n)\in S$. First associate to $\pi\in C_\lambda$ the sequence $(d_1,\ldots,d_n)$ by locating the largest elements of all orbits (cycles) of $\pi$, ordering the orbits by their largest element in increasing order, and taking the sizes of the orbits in that order. Then the last orbit, of size $d_n$, must contain the number $i$ (as its maximal element), and the number of possibilities for the last orbit is determined by the choices for the successive elements until the cycle closes, giving the falling product $$ (i-1)(i-2)\ldots(i-d_n+1)= \prod \{\,j\mid d_1+d_2+\cdots+d_{n-1}<j<i\,\}, $$ which is a sub-product of $P(d_1,\ldots,d_n)$. Once the last orbit is fixed, the largest remaining element must appear in the previous orbit, and any further elements of this orbit can be chosen in a number of ways again given by a falling product, this time starting with $d_1+d_2+\cdots+d_{n-1}-1$ and ending with $d_1+d_2+\cdots+d_{n-2}+1$. Continuing this way, one finds that the total number of permutations giving rise to $(d_1,\ldots,d_n)$ is $P(d_1,\ldots,d_n)$, which completes the proof.

share|improve this answer
    
First of all, thank you so much for your answer. It is hard for me to follow your answer as I am not familiar with the knowledge you use....I am trying to understand it and maybe I can discuss with you later...@_@ –  Chang Aug 27 '12 at 16:30
    
This is an amazing answer; I'd give it more than +1 if I could :-) –  joriki Aug 27 '12 at 19:41
    
It is really a remarkable answer, although I need time to fully understand it. Thank you so much for your prove. ^_^ –  Chang Aug 28 '12 at 14:32

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.