2-norm of the upper triangular "all-ones" matrix - MathOverflow

2-norm of the upper triangular "all-ones" matrix

2011-08-08T15:31:52Z

Let $M_n$ be the $n\times n$ matrix $$ (M_n)_{ij}=\begin{cases}1 & i\leq j,\\ 0 &i>j.\end{cases} $$ Is there around an explicit expression or at least an asymptotic for $\left\Vert M_n \right\Vert$? The norm is the usual Euclidean induced norm $\left\Vert M \right\Vert=\rho(M^TM)^{1/2}$.

I apologize if this a stupid question...

Answer by Geoff Robinson for 2-norm of the upper triangular "all-ones" matrix

2011-08-08T16:39:28Z

I calculate that we have $\sqrt{ \frac{(n+1)(2n+1)}{6}} \leq \|M_n \| \leq \sqrt{ \frac{n(n+1)}{2}}$, though it may be possible to do better. If we let $v_n$ denote the all $1$-vector of length $n$, then we have $\|M_n v_n \|^{2} = \sum_{j=1}^{n} j^{2} = \frac{n(n+1)(2n+1)}{6}.$ On the other hand, for any $n$-long vector $u$, we have $\|M_n u \|^{2} \leq n \|u \|^{2} + \|M_{n-1}\|^{2} \|u \|^{2}$ by using the Cauchy-Schwarz inequality for the first component to get the first term of the sum, and looking at the last $n-1$ components for the second term of the sum. Since $\| M_1 \| = 1,$ we see by induction that $\|M_n \|^2 \leq \frac{n(n+1)}{2}$. Later edit: Note that these crude estimates give $\frac{2n+1}{3.4642} < \|M_n \| < \frac{2n+1}{2.828},$ compared to the correct bound given by Noam Elkies which is asymptotically $\frac{2n+1}{\pi}.$

Answer by Noam D. Elkies for 2-norm of the upper triangular "all-ones" matrix

2011-08-08T18:32:05Z

The eigenvalues of $M^{\rm T}M$ are $1 / (4 \phantom. \cos^2\frac{k\pi}{2n+1})$ for $k=1,2,\ldots,n$. The largest of these arises for $k=n$ and equals $1/(4\phantom.\sin^2\frac{\pi}{4n+2})$. Hence $\|M\| = 1 / (2 \phantom.\sin\frac{\pi}{4n+2})$, which is asymptotic to $2n/\pi$. This is easier to see if we work not with $M$ but with its inverse, which is a unipotent matrix with $-1$'s on the first subdiagonal and $0$'s elsewhere.

EDIT Dividing by $n$ and letting $n \rightarrow \infty$, we also recover a form of Wirtinger's inequality: the operator $T$ on $L^2(0,1)$ taking a function $f$ to its indefinite integral [i.e. $Tf(x) = \int_0^x f(y) \phantom. dy$] has norm $2/\pi$, attained by $f(x) = \cos (\pi x /2)$. [To see the connection, compare the Riemann sums for $\|f\|_2^2 = \int_0^1 f(x)^2 dx$ and $\|Tf\|_2^2 = \int_0^1 (\int_0^x f(y) \phantom. dy)^2 dx$.]

Answer by Chris Godsil for 2-norm of the upper triangular "all-ones" matrix

2011-08-08T20:15:23Z

[This may be largely an alternate version of Noam's answer, but the extra context could be interesting.]

Let $N$ be the $m\times m$ matrix with $N_{i,i+1}=1$ for $i=1,\ldots,m-1$ and all other entries zero. Then the matrix $$ A = \begin{pmatrix}0&I+N\\ (I+N)^T&0 \end{pmatrix} $$ is the adjacency matrix of the path on $2m$ vertices. Now $$ A^{-1} = \begin{pmatrix} 0&(I+N)^{-1}\\ (I+N)^{-T}&0 \end{pmatrix} $$ and since $N^n=0$, $$ (I+N)^{-1} = I-N+\cdots+(-1)^{n-1}N^{n-1} $$ Let $D$ be the $2m\times 2m$ diagonal matrix with $D_{i,i}=(-1)^{i-1}$. Then it easy to check that $$ D^{-1}AD = \begin{pmatrix} 0&M\\ M^T&0 \end{pmatrix} $$ where $M$ is the matrix from the question. The 2-norm we want is the square of the largest eigenvalue of $D^{-1}AD$, which is the square of the largest eigenvalue of $A$, which is the square of the reciprocal of the $n$-th eigenvalue of the path on $2n$ vertices (which is its smallest positive eigenvalue).

The eigenvalues of the path on $n$ vertices are $2\cos\left(\frac{j\pi}{n+1}\right)$ for $j=1,\ldots,n$.

More on this appears in my old paper ``Inverses of trees''. (We can view $M$ as the incidence matrix of a chain, and so some of the above extends to a larger class of posets.)