Take the 2-minute tour ×

I have a question concerning matrix analysis.

let $A$ be the following $n \times n$-matrix with non-negative integer entries.

$$\begin{pmatrix}0&k_2&k_3&\dots&k_n\\ k_1&0&k_3&\dots&k_n\\ k_1&k_2&0&\dots&k_n\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ k_1&k_2&k_3&\dots&0\end{pmatrix}$$

i.e. the $j$-th row of $A$ is $(k_1,k_2,\dots k_n)-(0,0,...,k_j,0,0)$

How to express the norm of $A^n$ in terms of $k_1, k_2,\dots, k_n$ and the entries of $A^{(n-1)}$???

share|improve this question
Which norm?${}$ –  Gerry Myerson Oct 15 '12 at 0:41
either the induced norm or the frobenius norm, –  noot Oct 15 '12 at 1:53
I am asking the growth rate of the norm –  noot Oct 15 '12 at 1:53
Induced --- from what? –  Gerry Myerson Oct 15 '12 at 2:53

1 Answer 1

Deriving a relation for the frobenius norm should be easy.

Define $x_n=[k_1,k_2,\dots,k_n]^{T}$, then it is straight forward to see that $||A_n||_{F}^{2}=(n-1)||x_n||^2_{2}$. Using this recursive formula, one can derive that $||A_{n+1}||_{F}^{2}=||A_{n}||_{F}^{2}+||x_{n+1}||^2_{2}+(n-1)|k_{n+1}|^{2}$.

Deriving the induced norm case is slightly more involved. But may be this direction can help.

Define the matrix $T_n=ones(N,N)-I$ where $ones(N,N)$ is a $N \times N$ matrix with all entries as one and $I$ is the identity matrix. To get a feel of it, for $N=4$, \begin{align} T_4=\left[ \begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \right] \end{align} Define $D_n=diag(x_n)$ where $x_n$ is defined as earlier and $D_n$ is the diagonal matrix with $x_n$ as its diagonal entries. Note that now your matrix $A_n$ is


Note the observation that the singular values of $T_n$ are $(n-1,1,\dots,1)$. Consider the problem. \begin{align} \max_{||D_{n}^{-1}y||=1} ||T_ny||_{2} \end{align} I am not sure how exactly you can solve this. Once you can solve that deriving a relation between successive induced norms should be a easy matter.

share|improve this answer

Your Answer


