norm of power of matrix ---recursive formula

Question

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)}$???

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.