Euclidean volume of the unit ball of matrices under the matrix norm - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:54:27Z http://mathoverflow.net/feeds/question/1464 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm Euclidean volume of the unit ball of matrices under the matrix norm Samuel 2009-10-20T18:03:18Z 2010-02-01T06:11:45Z <p>The matrix norm for an n-by-n matrix A is defined as |A|=max(|Ax|) where x ranges over all vectors with |x|=1, and the norm on the vectors in R^n is the usual Euclidean one. This is also called the induced (matrix) norm, the operator norm, or the spectral norm. The unit ball of matrices under this norm can be considered as a subset of R^(n^2). What is the Euclidean volume of this set? I'd be interested in the answer even in just the 2-by-2 case.</p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1525#1525 Answer by Mike Hartglass for Euclidean volume of the unit ball of matrices under the matrix norm Mike Hartglass 2009-10-20T23:53:11Z 2009-10-20T23:53:11Z <p>Not that this is too helpful, but in the case of a 2 x 2 matrix A (with diagonal entries a and d and off diagonal entries b and c all real) the norm for the matrix is given by the formula $\frac{1}{2}(a^{2} + b^{2} + c^{2} + d^{2} + \sqrt{(a^{2} + b^{2} + c^{2} + d^{2})^{2} - 4D})$ where $D = det(A^{*}A)$. It is a pretty ugly region but at least it can be computed in terms of a, b, c, and d and this unit ball will sit inside the Euclidean ball in R^{4}. </p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1536#1536 Answer by George Lowther for Euclidean volume of the unit ball of matrices under the matrix norm George Lowther 2009-10-21T00:32:59Z 2009-10-21T21:04:11Z <p>I had a go at this question, but the method I tried here doesn't quite work out. It does reduce it to upper triangular matrices, although that doesn't seem to be a lot of help for general n.</p> <p>Let your volume be V.</p> <p>By scaling, the volume of the set {|A|&le;K} is VK<sup>n<sup>2</sup></sup>. Now let M be a matrix whose entries are independent normal random variables with mean 0 variance 1. From the density function of the normal distribution, this gives P(|M|&le;K)~(2&pi;)<sup>-n<sup>2</sup>/2</sup>VK<sup>n<sup>2</sup></sup> in the limit of small K.</p> <p>I'll now calculate this expression in an alternative way. Use the M=QR decomposition, where Q is orthogonal and R is upper triangular, with diagonal elements &lambda;<sub>n</sub>, &lambda;<sub>n-1</sub>,&hellip;&lambda;<sub>1</sub>, which are the eigenvalues of R. This can be done in such a way that &lambda;<sub>k</sub><sup>2</sup> has the <a href="http://en.wikipedia.org/wiki/Chi%5E2" rel="nofollow">&chi;<sup>2</sup><sub>k</sub>-distribution</a> (a quick google search gives <a href="http://www.nowpublishers.com/product.aspx?product=CIT&amp;doi=0100000001&amp;section=x1-36r1" rel="nofollow">this</a> but there's probably better references). The upper triangular parts of R have the standard normal density. We need to calculate |R|. I was originally thinking that this is the max eigenvalue, but it's not quite that simple.</p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1543#1543 Answer by Armin Straub for Euclidean volume of the unit ball of matrices under the matrix norm Armin Straub 2009-10-21T01:19:06Z 2009-10-21T01:47:38Z <p>Concerning the 2x2 case: As Mike points out, you can write down an explicit formula for the norm of the matrix {{a,b},{c,d}}. It takes a good while but Mathematica can then compute the volume you're asking for.</p> <pre><code>Integrate[If[a^2 + b^2 + c^2 + d^2 + Sqrt[((b+c)^2 + (a-d)^2) ((b-c)^2 + (a+d)^2)] &lt;= 2, 1, 0], {a, -1, 1}, {b, -1, 1}, {c, -1, 1}, {d, -1, 1}] </code></pre> <p>Its answer is: 2&pi;<sup>2</sup>/3.</p> <p>For comparison: the volume of the Euclidean ball in R<sup>4</sup> is &pi;<sup>2</sup>/2 (which contradicts Mike's final statement that the matrix norm ball sits inside the Euclidean one).</p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1569#1569 Answer by jc for Euclidean volume of the unit ball of matrices under the matrix norm jc 2009-10-21T03:18:43Z 2009-10-21T17:31:22Z <p>I worked out the answer for the 2 by 2 case as well.</p> <p>First, when dealing with 2 by 2 matrices in general, a convenient variable change is:</p> <pre><code>a-&gt;(w+x)/\sqrt{2},d-&gt;(w-x)/\sqrt{2},c-&gt;(y-z)/\sqrt{2},b-&gt;(y+z)/\sqrt{2}. </code></pre> <p>Then a^2+b^2+c^2+d^2 = w^2+x^2+y^2+z^2. And the determinant (ad-bc) = (1/2)*(x^2+y^2-w^2-z^2).</p> <p>(Aside: this set of coordinates lets you see for instance that the set of rank 1 matrices in the space of 2D matrices realized as R^4 is a cone over the Clifford torus, since x^2+y^2 = w^2+z^2 on a sphere x^2+y^2+w^2+z^2=r^2 implies x^2+y^2 = r^2/2 and w^2+z^2 = r^2/2, which are scaled equations for a flat torus)</p> <p>Let r1^2 = x^2+y^2, r2^2 = w^2+z^2. (These are radial coordinates of two cylindrical coordinate systems filling out 4-space). Then the norm squared is:</p> <pre><code>(1/2)*(r1^2+r2^2 + \sqrt{ (r1^2+r2^2)^2 - (r1^2-r2^2)^2 }) </code></pre> <p>When this is less than one, this corresponds to the region plotted below:</p> <p><img src="http://i583.photobucket.com/albums/ss275/jaspercrowne/spectralnormball2.png" alt="spectral norm ball" /></p> <p>Note that each point in the r1,r2 picture corresponds to a different "torus", x^2+y^2=r1^2, w^2+z^2=r2^2.</p> <p>We can now integrate over the shaded in region, \int_{region} dw dx dy dz.</p> <p>This 4-D integral can be reduced to 2D using r1 and r2, since dx dy = 2π r1 dr1, dw dz = 2π r2 dr2:</p> <pre><code>(4π^2) \int_{region} dr1 dr2 r1 r2 </code></pre> <p>Now, note that we can rewrite r2 in terms of r1. In particular, after some manipulation of our norm, the shaded in region is defined by r2^2 ≤ 2-2\sqrt{2}r1+r1^2=(\sqrt{2}-r1)^2. Hence r2≤ \sqrt{2}-r1, and we can evaluate the r2 integral:</p> <pre><code>(4π^2) \int_{r1=0}^\sqrt{2} dr1 r1 \int_{r2=0}^{\sqrt{2}-r1} r2 dr2 = (4π^2) \int_{r1=0}^\sqrt{2} dr1 r1 (\sqrt{2}-r1})^2/2 = (4π^2) (1/6) </code></pre> <p>This yields 2π^2/3, as Armin found.</p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1604#1604 Answer by David Bar Moshe for Euclidean volume of the unit ball of matrices under the matrix norm David Bar Moshe 2009-10-21T07:50:21Z 2010-02-01T06:04:22Z <p>By means of singular value decomposition, I think that the general answer for a real n by n matrix should be: Required volume = $${\rm vol}(O(n))^2 \int\limits_{0\leq s_n \leq s_{n-1}\leq \dots s_1\leq 1}\prod_{i &lt; j &lt; n} (s_ i^2-s_ j^2).$$</p> <p>O(n) is the n-dimensional orthogonal group</p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1611#1611 Answer by David Bar Moshe for Euclidean volume of the unit ball of matrices under the matrix norm David Bar Moshe 2009-10-21T08:34:51Z 2009-10-21T10:08:25Z <p>Yes, O(n) is the n(n-1)/2 dimensional space of orthogonal n by n matrices. Vol(O(n)) is its volume.</p> <p>The integrand in the answer is simply the Jacobian of the singular value decomposition, {s_ i} is just the ordered set of the singular value and the integration is performed on the subset bounded by 1. </p> <p>I may just have missed a factor of 1/2^n because of the sign ambiguity in the svd singular values</p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/1729#1729 Answer by Guillaume Aubrun for Euclidean volume of the unit ball of matrices under the matrix norm Guillaume Aubrun 2009-10-21T21:30:01Z 2010-02-01T06:06:52Z <p>The volume of the unit ball for the spectral norm in nxn real matrices is given by the formula</p> <p>$$c_n \int\limits_{[-1,1]^n} \prod_{i &lt; j} |x_i^2-x_j^2| dx_1\dots dx_n$$</p> <p>where $c_n = n! 4^{-n} \prod_{k=1}^n v_k^2$</p> <p>and $v_k=\pi^{k/2}/\Gamma(1+k/2)$ is the volume of the unit ball in R^n.</p> <p>A much more general formula for calculating all kind of similar quantities appears e.g. <a href="http://analysis.math.uni-kiel.de/koenig/inhalte/isotropy.pdf" rel="nofollow">here</a> (Lemma 1). The proof is by applying the SVD decomposition as a change of variables.</p> <p>The first values are</p> <ul> <li>2/3 &pi;<sup>2</sup> for 2x2 matrices</li> <li>8/45 &pi;<sup>4</sup> for 3x3 matrices</li> <li>4/1575 &pi;<sup>8</sup> for 4x4 matrices ...</li> </ul> <p>There might be a closed formula for the integral above. Edit : such a formula appears in Armin's post below !!</p> http://mathoverflow.net/questions/1464/euclidean-volume-of-the-unit-ball-of-matrices-under-the-matrix-norm/3151#3151 Answer by Armin Straub for Euclidean volume of the unit ball of matrices under the matrix norm Armin Straub 2009-10-28T22:05:39Z 2010-02-01T06:11:45Z <p>Building on the nice answer of Guillaume: The integral</p> <p>$$\int_{[-1,1]^n} \prod_{i &lt; j} |x_i^2 - x_j^2 | dx_1\dots dx_n$$</p> <p>has the closed-form evaluation</p> <p>$$4^n \prod_{k \leq n} \binom{2k}{k}^{-1}.$$</p> <p>This basically follows from the evaluation of the <a href="http://en.wikipedia.org/wiki/Selberg%5Fintegral" rel="nofollow">Selberg beta integral</a> S<sub>n</sub>(1/2,1,1/2).</p> <p>Combined with modding out by a typo, we now arrive at the following product formula for the volume of the unit ball of nxn matrices in the matrix norm:</p> <p>$$n! \prod_{k\leq n} \frac{ \pi^k }{ ((k/2)! \binom{2k}{k})} .$$</p> <p>In particular, we have:</p> <ul> <li>2/3 &pi;<sup>2</sup> for n=2</li> <li>8/45 &pi;<sup>4</sup> for n=3</li> <li>4/1575 &pi;<sup>8</sup> for n=4</li> </ul>