Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I asked this question on math.stackexchange and haven't received an answer in two weeks, so I'm repeating it here.

Let

$$ H=\left(\begin{array}{cccc} 0 & 1/2 & 0 & 1/2 \cr 1/2 & 0 & 1/2 & 0 \cr 1/2 & 0 & 0 & 1/2\cr 0 & 1/2 & 1/2 & 0 \end{array}\right), $$

$K_1(\alpha)=\left(\begin{array}{c}1 \\\\ \alpha\end{array}\right)$ and consider the sequence of matrices defined by $$ K_L(\alpha) = \left[H\otimes I_{2^{L-2}}\right]\left[I_2 \otimes K_{L-1}(\alpha)\right], $$ where $\otimes$ denotes the Kronecker product, and $I_n$ is the $n\times n$ identity matrix.

I am interested in the limiting behaviour of the singular values of $K_L(\alpha)$ -- in particular, $K_L(0)$ -- as $L$ tends to infinity. Some calculation indicate that the $2^L\times 2^{L-1}$-matrix $K_L$ has $L$ non-zero singular values and that, for any positive integer $k$, the $k$ largest singular values converges to some limit.

Question: Can this limit be described in terms of the matrix $H$?

I did some experiments and it seems that the limiting behaviour of the singular values of $K_L$ does not only depend on the matrix $H$, but also on the initial value $K_1(\alpha)$. This makes it unlikely for fixed-point arguments to work in this setting.

I also tried to obtain combinatorial expressions for the coefficients in the characteristic polynomial $\chi_L^\alpha(\lambda)$ of $K_L(\alpha)K_L(\alpha)^T$ but was successful only for the three highest non-trivial powers of $\lambda$.

Edit:

The analysis of $\Sigma(\alpha):=\lim_{L\to\infty}\sigma_1(K_L(\alpha))$ as a function of $\alpha$, as suggested by Suvrit, seems to be a good idea. Numerical calculations indicate that, asymptotically, $$ \Sigma(\alpha)\sim \Sigma(0)\left(.3540+\alpha\right),\quad \alpha\to\infty,\quad \Sigma(0)\approx .8254, $$ and that $\Sigma(\alpha)$ has a minimum at $\approx(-.2936,.7696)$.

I do not see yet, however, if this can be used to compute $\Sigma(0)$ more precisely.

Edit:

Using the improved bound $\sigma_1(K_L)\leq \frac{1}{2}\sqrt{3+2\alpha +3 \alpha ^2}$, which is sharp for $\alpha=\pm 1$, we can deduce that $d/d\alpha \Sigma(-1)=-1/2$, and $d/d\alpha \Sigma(1)=1/\sqrt{2}$.

Edit3:

After staring at the problem a little longer I've come up with a conjecture for the characteristic polynomial $\chi_L^{\alpha}(\lambda)$ of $K_L(\alpha)K_L(\alpha)^T$. More precisely, I believe that $$ \lambda^{-2^L+L}\chi_L^{\alpha}(\lambda) =\lambda ^L-\left(1+\alpha ^2\right)\lambda ^{L-1}+\\\\ +\frac{1}{2^L-1}\sum _{k=2}^L \left(-2\right)^{-k}\left[(1-\alpha)^{2(k-1)}\right]\left[(1-\alpha )^2+k (1+\alpha )^2 \right]\frac{(2^{-L};2)_k}{[k]_2!}\left(2^k-2+2^L\right)\lambda^{L-k}, $$ where $(a;q)_k$ denotes a q-Pochhammer symbol and $[k]_q!$ denotes a q-factorial.

It appears that this formula implies that $\lim_{L\to\infty}\sigma_1(K_L(0))$ can be characterized as $\kappa^{-1/2}$, where $\kappa$ is the smallest positive zero of $x\mapsto f(-x/2)$ and $$ f:x\mapsto\sum_{k=0}^\infty{\frac{(k+1)x^k}{[k]_2!}}. $$ Interestingly, this function is related to the q-exponential.

More generally, $\lim_{L\to\infty}\sigma_1(K_L(\alpha))$ can apparently be characterized as $\kappa_\alpha^{-1/2}$, where $\kappa_\alpha$ is the smallest positive solution of $x\mapsto f_\alpha(-x/2)=0$ and $$ f_\alpha:x\mapsto\sum_{k=0}^\infty{\frac{(1-\alpha )^{2 (k-1)} \left[(1-\alpha )^2+k (1+\alpha )^2\right]x^k}{[k_2]!}}. $$ The other singular values are similarly obtained from the remaining zeros of $x\mapsto f_\alpha(-x/2)$.

The next task will be to say something about the singular vectors.

share|improve this question
    
Hi Eckhard: please see my comment to my answer below... –  Suvrit Jan 8 '13 at 17:33
    
Hi Eckhard: Please feel free to "unaccept" my answer as it is only partial--- –  Suvrit Jan 9 '13 at 20:36
add comment

1 Answer

up vote 3 down vote accepted

Revised to include details of general $\alpha$


While not a complete answer, here are some ideas that may be of interest.

Define $\theta = (1+\alpha)^2$.

To ease notation, I'll write $K_L$ to mean $K_L(\alpha)$. Some experimentation reveals a nice pattern satisfied by $M_L := K_L^TK_L$. In particular, we see that $M_L$ is comprised of two numbers, $\frac{\theta}{2^L}$ and $\frac{2\theta}{2^L}$, which occur in a well-structured pattern. We seek to bound the Perron-Frobenius root, say $\rho$ of the nonnegative matrix $M_L$. Looking at the pattern of $M_L$ we see that the smallest possible column sum of $M_L$ happens when $\theta$ arises $2^{L-1}-1$ times and $2\theta$ arises once. Thus, we see that \begin{equation*} \rho \ge (2^{L-1}-1)\frac{\theta}{2^L} + \frac{2\theta}{2^L} = \theta\left(\frac{1}{2}+\frac{1}{2^L}\right). \end{equation*}

Similarly, by looking at the pattern, we see that the largest row-sum happens when $\theta$ appears $2^{L-2}$ times and $2\theta$ appears $2^{L-1}-2^{L-2}$ times (noting that $M_L$ is of size $2^{L-1} \times 2^{L-1}$). Thus, we see that \begin{equation*} \rho \le 2^{L-2}\frac{\theta}{2^L} + (2^{L-1}-2^{L-2}) \frac{2\theta}{2^L} = \frac{3}{4}\theta. \end{equation*}

Example, when $\alpha=0$, then $\theta=1$, and the upper bound on $\sigma_1(K_L) = \sqrt{\rho} \le \sqrt{3/4}$, otherwise, we get \begin{equation*} \sigma_1(K_L) \le (1+\alpha)\sqrt{\frac{3}{4} }. \end{equation*}

As I noted previously, a more careful analysis is needed to refine these bounds and to characterize how the limiting value is achieved (perhaps we can leverage $K_L$ being a column stochastic matrix?), but this bound is numerically not too bad. For example, a quick numerical experiment shows that $\sigma_1(K_L(0)) \to 0.8254....$ very rapidly (already for $K_7$, the first 4 digits match).

share|improve this answer
    
@Suvrit: Thank you for your answer. Indeed, $\sigma_1(K_2(0))=\sqrt{3/4}$, and after that the sequence $(\sigma_1(K_L(0)))_L$ seems to be decreasing. Do you see a way to characterize the limit more precisely, as alluded to in your last sentence? –  Eckhard Dec 29 '12 at 22:32
    
Certainly a closer characterization should be possible because the $K_L$ are column stochastic matrices that evolve with $L$ in a fairly regular way; if I get some time, I'll think a bit about this problem; otherwise, numerical experiments will offer a good "guess" that approximates the limit as a function of $\alpha$. –  Suvrit Dec 30 '12 at 9:38
    
@Suvrit: Is it possible that you meant to write in your analysis that $2^LM_L$ is comprised of the two numbers $\theta=(1+\alpha)^2$ and $2(1+\alpha^2)$, as opposed to $\theta$ and $2\theta$? This would lead to the bound $\sigma_1(K_L)\leq \frac{1}{2}\sqrt{3+2\alpha +3 \alpha ^2}$, which is tighter and indeed sharp for $\alpha=\pm 1$. –  Eckhard Jan 7 '13 at 22:04
    
@Eckhard: Sorry for the confusion; indeed, I meant $(1+a)^2$ and $2(1+a^2)$, not $\theta$ and $2\theta$ (stupid carry-over typo on my part!). thanks for catching this error! as soon as i get a chance, i'll edit my answer to reflect this correction. –  Suvrit Jan 8 '13 at 17:32
add comment

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.