# 2-norm of the upper triangular “all-ones” matrix

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

-
The following inequalities are very easy: $E(n/2) \leq \|M_n\| \leq n$ (where $E(\cdot)$ is the integer part). They follow from the fact that the norm of the all-ones matrix is $n$. But it is perhaps possible to get an exact formula. –  Mikael de la Salle Aug 8 '11 at 15:53
It seems that $\|M_n\| \approx (8/25)[2n+1]$ –  Suvrit Aug 8 '11 at 16:49

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

-
Excellent! Thanks. –  Federico Poloni Aug 8 '11 at 18:53
ah, the inverse trick again at play! –  Suvrit Aug 8 '11 at 19:14
Suvrit is alluding to mathoverflow.net/questions/68099 . I was reminded of that problem too. But here experiments with small $n$ suggested that the characteristic polynomial, even if irreducible, has a cyclic Galois group, suggesting that there might be a closed form for the eigenvalues. When this closed form then turned out to involve reciprocals of the basic trig functions it became natural to consider $1/M$. –  Noam D. Elkies Aug 8 '11 at 21:11
Thanks Noam for sharing your insights behind how you approached this problem; your the path to the answer seems to me to be as interesting as the answer itself. –  Suvrit Aug 8 '11 at 22:05

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

-

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

-
the upper bound does not really need induction; simply note $\|M_n\|_2 \le \|M_n\|_F$; using $\|M_n\|_F \le \sqrt{n}\|M_n\|_2$ another easy lower bound is possible. –  Suvrit Aug 8 '11 at 16:57