If matrix $A$ has entries $A_{ij}=\sin(\theta_i - \theta_j)$, why does $\|A\|_* = n$ always hold?

Solution 1:

I will stick to your notation in which $f(X)$ refers to the matrix whose entries are $f(X_{ij})$.

Note that by Euler's formula, we have $$ \sin(X) = \frac 1{2i}[\exp(iX) - \exp(-iX)] $$ To see that $\exp(iX)$ has rank $1$, we note that it can be written as the matrix product $$ \exp(iX) = \pmatrix{\exp(i\theta_1) \\ \vdots \\ \exp( i\theta_n)} \pmatrix{\exp(-i\theta_1) & \cdots & \exp( -i\theta_n)} $$ Verify also that $\exp(iX)$ is Hermitian (and positive definite), as is $\exp(-iX)$.

So far, we can conclude that $\sin(X)$ has rank at most equal to $2$.

Since $\exp(iX)$ is Hermitian with rank 1, we can quickly state that $$ \|\exp(iX)\|_* = |\operatorname{tr}(\exp(iX))| = n $$ So, your numerical evidence seems to confirm that $$ \left\|\frac 1{2i}[\exp(iX) - \exp(-iX)]\right\|_* = \left\|\frac 1{2i}\exp(iX)\right\|_* + \left\|\frac 1{2i}\exp(-iX)\right\|_* $$

From there, we note that $A = \sin(X)$ satisfies $$ 4 A^*A = [\exp(iX) - \exp(-iX)]^2 = \\ n [\exp(iX) + \exp(-iX)] - \exp(iX)\exp(-iX) - \exp(-iX)\exp(iX) =\\ n [\exp(iX) + \exp(-iX)] - 2 \operatorname{Re}[\exp(iX)\exp(-iX)] $$ where the exponent here is used in the sense of matrix multiplication. Our goal is to compute $\|A\|_* = \operatorname{tr}(\sqrt{A^*A})$.

Potentially useful observations:

We note that $$ \exp(iX)\exp(-iX) = \pmatrix{\exp(i\theta_1) \\ \vdots \\ \exp( i\theta_n)}\pmatrix{\exp(i\theta_1) & \cdots & \exp( i\theta_n)} \sum_{k=1}^n \exp(-2i\theta_k) $$ And $\operatorname{tr}[\exp(iX)\exp(-iX)] = \left| \sum_{k=1}^n \exp(2i\theta_k) \right|^2$. This product is complex-symmetric but not Hermitian.

The matrices $\exp(iX),\exp(-iX)$ will commute if and only if $\exp(iX)\exp(-iX)$ is purely real (i.e. has imaginary part 0).

I think that these matrices will commute if and only if $\sum_{k=1}^n \exp(2i\theta_k) = 0$ (which is not generally the case).

Solution 2:

Unfortunately, your hypotheses are a little too good to be true in general. But they do hold exactly in the special case that $\sum_i e^{2\theta_i}=0$ This will be the case when, for example, the angles are evenly spaced on the circle, i.e. $\theta_i=i*2\pi/n$. Moreover, they hold approximately in the limit of a large number of points sampled uniformly and independently.

Any $\theta$ with $n=2$ will provide a counterexample to the claim about the singular values of $cos(X)$, provided that $\cos(\theta_1-\theta_2)\ne 0$. Indeed, since the matrix is symmetric, the singular values and eigenvalues coincide, and the only way that both eigenvalues of a 2x2 matrix can be equal is if the matrix is diagonal.

Now let's see why the statement about singular values is approximately true.

Indeed, using standard angle addition formulas, we see that $\sum_i \cos(\theta_i-\theta_j)\cos(\theta_i)=.5\sum_i\cos(2\theta_i-\theta_j)+\cos(\theta_j)=.5n\cos(\theta_j)+.5\sum_i\cos(2\theta_i-\theta_j)$

By the law of large numbers, we have $\sum_i\cos(2\theta_i-\theta_j)\approx {\frac n{2\pi}} \int_0^{2\pi}\cos(2\theta-\theta_j)d\theta=0$ for large $n$. Therefore, in the limit of many independently uniformly sampled angles, the vector $\cos(\theta)$ is an eigenvector of $cos(X)$ with eigenvalue $.5n$. Similarly, one may check that $\sin(\theta)$ is likewise an eigenvector in the limit with the same eigenvalue. I suspect this argument carries over to the matrices $\sin(X)$ and $\cos(X)\circ\sin(X)$, although I haven't worked out the details. Furthermore, if we assume that $\sum_i e^{2\theta_i}=0$, then the above computations shows that $\cos(\theta)$ and $\sin(\theta)$ are exact eigenvectors with eigenvalues $\pm n/2$.

Edit: The statements about the nuclear norm holds for cos(X), but not sin(X). Indeed, the matrix cos(X) is symmetric and non-negative definite, so its nuclear norm is equal to its trace, which is $\sum_i \cos(\theta_i-\theta_i)=n$.

As for sin(X), the statement about the nuclear norm does not hold exactly, but it does hold when $\sum_i e^{2\theta_i}=0$, as well as approximately in the limit of many uniformly and indepdnently sampled phases, as before. Indeed, the matrix sin(X) is antisymmetric, so it can be unitarily diagonalized (over the complex numbers), with purely imaginary eigenvalues coming in conjugate pairs. The magnitudes of these eigenvalues are in turn the real singular values (up to a sign, which is immaterial for computing the norm). As Omnomnomnom has already pointed out, we may write $sin(X)$ as the sum of two complex rank-1 matrices, namely $e^{i\theta}\otimes e^{-i\theta}/2i$ and its complex conjugate (here $\otimes$ denotes the outer product of two vectors). The vectors $e^{i\theta}$ and $e^{-i\theta}$ are not orthogonal in general (with respect to the hermitian innner product), so this is not a unitary decomposition.

However, it is nearly a unitary given the previous assumptions on $\theta$. Indeed, we see that $\mid e^{i\theta}\mid=\sum_i \mid e^{i\theta_i}\mid^2=n$. Furthermore, one may verify that for large $n$, $<e^{i\theta},e^{-i\theta}>\to 0$, using the law of large numbers as before.

Setting $v=e^{i\theta}/\sqrt{n}$ and $w=e^{-i\theta}/\sqrt{n}$ we have $sin(X)=-inv\otimes w/2+inw\otimes v/2$. Since $v$ and $w$ both have unit norm and $<v,w>=<e^{i\theta},e^{-i\theta}>/n\approx 0$, this is approximately a unitary decomposition with eigenvalues $\pm in/2$. As per the earlier discussion, this implies that the singular values of $sin(X)$ are approximately $\pm n/2$, and the nuclear norm is correspondingly approximately $n$. I leave consideration of the matrix $A\circ B$ as an exercise to you.