4
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .