Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this 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
2  
It seems that $\|M_n\| \approx (8/25)[2n+1]$ –  Suvrit Aug 8 '11 at 16:49
add comment

3 Answers

up vote 17 down vote accepted

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

share|improve this answer
    
Excellent! Thanks. –  Federico Poloni Aug 8 '11 at 18:53
    
ah, the inverse trick again at play! –  Suvrit Aug 8 '11 at 19:14
3  
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
2  
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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