9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Aug 8, 2011 at 15:53
  • 2
    $\begingroup$ It seems that $\|M_n\| \approx (8/25)[2n+1]$ $\endgroup$
    – Suvrit
    Aug 8, 2011 at 16:49

3 Answers 3

20
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ ah, the inverse trick again at play! $\endgroup$
    – Suvrit
    Aug 8, 2011 at 19:14
  • 4
    $\begingroup$ 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$. $\endgroup$ Aug 8, 2011 at 21:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – Suvrit
    Aug 8, 2011 at 22:05
  • $\begingroup$ Thanks for this answer! Do you have any hint on how to find the eigenvalues of $M^TM$? $\endgroup$ Mar 28, 2016 at 14:22
6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Aug 8, 2011 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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