8
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Anyone helps? ::>_<:: $\endgroup$
    – Chang
    Aug 26, 2012 at 14:42
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 27, 2012 at 5:23
  • $\begingroup$ 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.... $\endgroup$
    – Chang
    Aug 27, 2012 at 8:46
  • 1
    $\begingroup$ 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] $$ $\endgroup$
    – Chang
    Aug 27, 2012 at 12:13
  • 1
    $\begingroup$ 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$. $\endgroup$ Aug 27, 2012 at 12:29

1 Answer 1

9
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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...@_@ $\endgroup$
    – Chang
    Aug 27, 2012 at 16:30
  • $\begingroup$ This is an amazing answer; I'd give it more than +1 if I could :-) $\endgroup$
    – joriki
    Aug 27, 2012 at 19:41
  • $\begingroup$ It is really a remarkable answer, although I need time to fully understand it. Thank you so much for your prove. ^_^ $\endgroup$
    – Chang
    Aug 28, 2012 at 14:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .