15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've posted a problem mathoverflow.net/questions/310498/… , which appears to be an interesting extension of the question posed by Samuel. Now, the $2 \times 2$ matrices are parameterized by a variable $\varepsilon \in [0,1]$, with the case $\varepsilon =1$ corresponding to the question having been asked above. The problem has been formally solved (by Lovas and Andai) when the entries of the matrices are in $\mathbb{R}$, and apparent solutions (but not yet proofs) for $\mathbb{C}$ and $\mathbb{H}$ given. $\endgroup$ – Paul B. Slater Sep 16 '18 at 21:13
9
$\begingroup$

Building on the nice answer of Guillaume: The integral

$$ \int_{[-1,1]^n} \prod\_{i < j} |x_i^2 - x_j^2 | dx_1\dots dx_n $$

has the closed-form evaluation

$$ 4^n \prod_{k \leq n} \binom{2k}{k}^{-1}.$$

This basically follows from the evaluation of the Selberg beta integral Sn(1/2,1,1/2).

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:

$$ n! \prod_{k\leq n} \frac{ \pi^k }{ ((k/2)! \binom{2k}{k})} .$$

In particular, we have:

  • 2/3 π2 for n=2
  • 8/45 π4 for n=3
  • 4/1575 π8 for n=4
$\endgroup$
  • $\begingroup$ "modding out by a typo" is very charming! $\endgroup$ – paul garrett Jul 24 '17 at 23:28
14
$\begingroup$

The volume of the unit ball for the spectral norm in nxn real matrices is given by the formula

$$ c_n \int\limits_{[-1,1]^n} \prod_{i < j} |x_i^2-x_j^2| dx_1\dots dx_n $$

where $c_n = n! 4^{-n} \prod_{k=1}^n v_k^2$

and $v_k=\pi^{k/2}/\Gamma(1+k/2)$ is the volume of the unit ball in R^n.

A much more general formula for calculating all kind of similar quantities appears e.g. here (Lemma 1). The proof is by applying the SVD decomposition as a change of variables.

The first values are

  • 2/3 π2 for 2x2 matrices
  • 8/45 π4 for 3x3 matrices
  • 4/1575 π8 for 4x4 matrices ...

There might be a closed formula for the integral above. Edit : such a formula appears in Armin's post below !!

$\endgroup$
  • $\begingroup$ When using your formula I get 1/3 Pi^2 for 2x2 matrices and the values for n=3,4 are different from the ones you give as well. Is there a small typo somewhere (or am I just messing up the calculation)? $\endgroup$ – Armin Straub Oct 22 '09 at 20:20
  • $\begingroup$ I doubled-checked and the general formula seems corrects (anyway you can derive it from the paper I quoted). But you are right, there was a typo for n=4 (now corrected). By the way, you should find c_2=pi^2/4 ; c_3=pi^4/9 ; c_4=pi^8/144. $\endgroup$ – Guillaume Aubrun Oct 23 '09 at 21:47
  • $\begingroup$ Looking at the paper I found the typo: c_n = n! 4^{-n} ... Also, your quite right; the integral does have a nice closed form coming from writing it as a Selberg integral. I put details into a new answer. $\endgroup$ – Armin Straub Oct 28 '09 at 22:10
  • $\begingroup$ Oops you're right ... $\endgroup$ – Guillaume Aubrun Oct 28 '09 at 22:48
3
$\begingroup$

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.

Integrate[If[a^2 + b^2 + c^2 + d^2
 + Sqrt[((b+c)^2 + (a-d)^2) ((b-c)^2 + (a+d)^2)] <= 2, 1, 0],
{a, -1, 1}, {b, -1, 1}, {c, -1, 1}, {d, -1, 1}]

Its answer is: 2π2/3.

For comparison: the volume of the Euclidean ball in R4 is π2/2 (which contradicts Mike's final statement that the matrix norm ball sits inside the Euclidean one).

$\endgroup$
  • $\begingroup$ My apologies, it is actually easy to see that the matrix norm ball does not sit inside the Euclidean one. The identity matrix clearly does the job. $\endgroup$ – Mike Hartglass Oct 21 '09 at 1:58
  • $\begingroup$ Nice example. At least it sits inside the max norm unit ball (filling it out by an ambitious 41% ...). $\endgroup$ – Armin Straub Oct 21 '09 at 11:12
  • $\begingroup$ I'd like to see the Mathematica code when the 2 x 2 matrices have complex entries. The answer, I believe, should then be $\frac{\pi^4}{6}$. $\endgroup$ – Paul B. Slater Mar 5 '17 at 16:53
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There should be a square root outside that expression, right? $\endgroup$ – j.c. Oct 21 '09 at 0:16
  • $\begingroup$ yes, I forgot the square root (or at least the lack of a square root is a typo in Conway's book). $\endgroup$ – Mike Hartglass Oct 21 '09 at 2:03
1
$\begingroup$

Yes, O(n) is the n(n-1)/2 dimensional space of orthogonal n by n matrices. Vol(O(n)) is its volume.

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.

I may just have missed a factor of 1/2^n because of the sign ambiguity in the svd singular values

$\endgroup$
  • 1
    $\begingroup$ The volume of the unit ball for the spectral norm in $2 \times 2$ real matrices is, as indicated above,$\frac{2 \pi^2}{3}$, while for $2 \times 2$ complex matrices it is $\frac{\pi^4}{6}$ (see Table 2, p. 7, in arxiv.org/pdf/1610.01410.pdf ). I would like to know the corresponding value for the $2 \times 2$ quaternionic matrices. $\endgroup$ – Paul B. Slater Jun 26 '17 at 18:06
1
$\begingroup$

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.

Let your volume be V.

By scaling, the volume of the set {|A|≤K} is VKn2. 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|≤K)~(2π)-n2/2VKn2 in the limit of small K.

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 λn, λn-1,…λ1, which are the eigenvalues of R. This can be done in such a way that λk2 has the χ2k-distribution (a quick google search gives this 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.

$\endgroup$
1
$\begingroup$

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 < j < n} (s_ i^2-s_ j^2).$$

O(n) is the n-dimensional orthogonal group

$\endgroup$
  • $\begingroup$ Is vol(O(n)) the n(n-1)/2-dimensional measure of the set of orthogonal n by n matrices? I would like to see how you came up with this. $\endgroup$ – Darsh Ranjan Oct 21 '09 at 8:15
1
$\begingroup$

I worked out the answer for the 2 by 2 case as well.

First, when dealing with 2 by 2 matrices in general, a convenient variable change is:

$$a\rightarrow\frac{w+x}{\sqrt{2}},d\rightarrow\frac{w-x}{\sqrt{2}},c\rightarrow\frac{y-z}{\sqrt{2}},b\rightarrow\frac{y+z}{\sqrt{2}}.$$

Then $a^2+b^2+c^2+d^2 = w^2+x^2+y^2+z^2$. And the determinant $(ad-bc) = \frac{1}{2}(x^2+y^2-w^2-z^2)$.

(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 $\mathbb{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)

Let $r_1^2 = x^2+y^2, r_2^2 = w^2+z^2$. (These are radial coordinates of a coordinate system consisting of two orthogonal 2D cylindrical coordinate systems). Then the norm squared is:

$$\frac{1}{2}\left(r_1^2+r_2^2 + \sqrt{ (r_1^2+r_2^2)^2 - (r_1^2-r_2^2)^2 }\right)$$

When this is less than one, this corresponds to the region plotted below:

spectral norm ball

Note that each point in the $r_1,r_2$ picture corresponds to a different "torus", $x^2+y^2=r_1^2, w^2+z^2=r_2^2$.

We can now integrate over the shaded in region, $\int_{region} dw dx dy dz$.

This 4-D integral can be reduced to 2D using $r_1$ and $r_2$, since $dx dy = 2\pi r_1 dr_1, dw dz = 2\pi r_2 dr_2$:

$$(4\pi^2) \int_{region} dr_1 dr_2 r_1 r_2. $$

Now, note that we can rewrite $r_2$ in terms of $r_1$. In particular, after some manipulation of our norm, the shaded-in region is defined by $r_2^2 \leq 2-2\sqrt{2}r_1+r_1^2=(\sqrt{2}-r_1)^2$. Hence $r_2\leq \sqrt{2}-r_1$, and we can evaluate the $r_2$ integral:

$$4\pi^2 \int_{r_1=0}^\sqrt{2} dr_1 r_1 \int_{r_2=0}^{\sqrt{2}-r_1} r_2 dr_2 \\ = 4\pi^2 \int_{r_1=0}^\sqrt{2} dr_1 r_1 (\sqrt{2}-r_1)^2/2\\ = (4\pi^2) (1/6).$$

This yields $2\pi^2/3$, as Armin found.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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