2-norm of the upper triangular "all-ones" matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T18:45:55Z http://mathoverflow.net/feeds/question/72361 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72361/2-norm-of-the-upper-triangular-all-ones-matrix 2-norm of the upper triangular "all-ones" matrix Federico Poloni 2011-08-08T15:31:52Z 2011-08-09T07:46:39Z <p>Let $M_n$ be the $n\times n$ matrix $$(M_n)_{ij}=\begin{cases}1 &amp; i\leq j,\\ 0 &amp;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}$.</p> <p>I apologize if this a stupid question...</p> http://mathoverflow.net/questions/72361/2-norm-of-the-upper-triangular-all-ones-matrix/72372#72372 Answer by Geoff Robinson for 2-norm of the upper triangular "all-ones" matrix Geoff Robinson 2011-08-08T16:39:28Z 2011-08-09T07:46:39Z <p>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} &lt; \|M_n \| &lt; \frac{2n+1}{2.828},$ compared to the correct bound given by Noam Elkies which is asymptotically $\frac{2n+1}{\pi}.$</p> http://mathoverflow.net/questions/72361/2-norm-of-the-upper-triangular-all-ones-matrix/72383#72383 Answer by Noam D. Elkies for 2-norm of the upper triangular "all-ones" matrix Noam D. Elkies 2011-08-08T18:32:05Z 2011-08-09T00:05:47Z <p>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.</p> <p><strong>EDIT</strong> 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$.]</p> http://mathoverflow.net/questions/72361/2-norm-of-the-upper-triangular-all-ones-matrix/72393#72393 Answer by Chris Godsil for 2-norm of the upper triangular "all-ones" matrix Chris Godsil 2011-08-08T20:15:23Z 2011-08-08T20:15:23Z <p>[This may be largely an alternate version of Noam's answer, but the extra context could be interesting.]</p> <p>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&amp;I+N\\ (I+N)^T&amp;0 \end{pmatrix}$$ is the adjacency matrix of the path on $2m$ vertices. Now $$A^{-1} = \begin{pmatrix} 0&amp;(I+N)^{-1}\\ (I+N)^{-T}&amp;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&amp;M\\ M^T&amp;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).</p> <p>The eigenvalues of the path on $n$ vertices are $2\cos\left(\frac{j\pi}{n+1}\right)$ for $j=1,\ldots,n$.</p> <p>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.)</p>