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

  • 3
    $\begingroup$ Which norm?${}$ $\endgroup$ – Gerry Myerson Oct 15 '12 at 0:41
  • $\begingroup$ either the induced norm or the frobenius norm, $\endgroup$ – noot Oct 15 '12 at 1:53
  • $\begingroup$ I am asking the growth rate of the norm $\endgroup$ – noot Oct 15 '12 at 1:53
  • 2
    $\begingroup$ Induced --- from what? $\endgroup$ – Gerry Myerson Oct 15 '12 at 2:53

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.