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 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
3  
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
2  
Induced --- from what? –  Gerry Myerson Oct 15 '12 at 2:53
add comment

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

$A_n=T_nD_n$

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