23
$\begingroup$

Can you help to find eigenvalues and eigenvectors of the following matrix?

Here is the matrix:

$$C = \small \begin{pmatrix} -\sin(\theta_{2} - \theta_{M}) & \sin(\theta_{1} - \theta_{M}) & 0 & \ldots & 0 & \sin(\theta_{2} - \theta_{1}) \\ \sin(\theta_{3} - \theta_{2}) & -\sin(\theta_{3} - \theta_{1}) & \sin(\theta_{2} - \theta_{1}) & \ldots & 0 & 0 \\ 0 & \sin(\theta_{4} - \theta_{3}) & -\sin(\theta_{4} - \theta_{2}) & \ldots & 0 & 0 \\ 0 & \ddots & \ddots & \ddots & \ddots & \vdots\\ \sin(\theta_{M} - \theta_{M - 1}) & 0 & 0 & \ldots & \sin(\theta_{1} - \theta_{M}) & -\sin(\theta_{1} - \theta_{M - 1}) \\ \end{pmatrix} $$

where $0 = \theta_{1} < \ldots < \theta_{M} < 2 \pi$. I have found 2 vectors for eigenvalue 0:

$$ v_{1} = (1, \cos(\theta_{1}), \ldots, \cos(\theta_{M - 1}))^{T} $$

$$ v_{2} = (0, \sin(\theta_{1}), \ldots, \sin(\theta_{M - 1}))^{T} $$

In case $\theta_{j} = \frac{2 \pi (j - 1)}{M}, \; j = 1, \ldots, M$ the matrix becomes circulant matrix, and it's obvious to find all its eigenvectors and eigenvalues.


If it's essential for somebody, I can explain the application where this matrix appears. In article by Lele, Kulkarni, Willsky - "Convex-polygon estimation from support-line measurements" this matrix represents the conditions of consistent support function measurements.

Each $i$-th row of matrix represent conditions that $i$-th descrete radius of curvature is positive. These are the criteria of consistency.


Here is the detailed description of geometrical interpretation of this matrix.

Defintion 1. The support function of convex body $K$ in $\mathbb{R}^{n}$ is defined as follows:

$$ h_{K}(u) = \sup \limits_{x \in K} (x, u) $$

Each value of support function corresponds to 1 support hyperplane of convex body.

Suppose that $n = 2$ (we work in plane). Maybe this picture will help you to understand what we are speaking about:

enter image description here

We consider $M$ measurements $h_{1}, \ldots, h_{M}$ of support function at directions $u_{1}, u_{2}, \ldots, u_{M}$ (all $||u_{j}|| = 1$, and $u_{j} = (\cos \theta_{j}, \sin \theta_{j}$)), and want to reconstruct the body $K$ from these measurements. In ideal, we can just intersect half-spaces corresponding to support hyperspaces:

$$ K = \bigcap \limits_{i = 1}^{M} \{x \in \mathbb{R}^{n} : \; (x, u_{i}) < (h_{i}, u_{i})\} $$

But measurements are noisy, so there could be no convex body that has such support function values at these directions. So we need to correct them. To do this we need some conditions representing the consistency of support function measurements.

Here are these conditions:

Theorem 1. A vector $h \in \mathbb{R}^{M}$ is the vector of support function measurements of some convex body if an only if

$$ C h \geq 0 $$

The value $h_{i - 1} \sin(\theta_{i + 1} - \theta_{i}) - h_{i} \sin(\theta_{i + 1} - \theta_{i - 1}) + h_{i + 1} \sin(\theta_{i} - \theta_{i - 1})$ is the value of $i$-th descrete radius of curvature. If all these values are positive, then the measurements are consistent.

The vectors

$$ v_{1} = (1, \cos(\theta_{1}), \ldots, \cos(\theta_{M - 1}))^{T} $$

$$ v_{2} = (0, \sin(\theta_{1}), \ldots, \sin(\theta_{M - 1}))^{T} $$

are just vectors of support function values of convex bodies consisting only from one point: $(1, 0)$ for $v_{1}$ and $(0, 1)$ for $v_{2}$.

Adding these vectors and their combinations to other support function measurements does not change descrete radio of curvature and correspond to translation of the convex body in $\mathbb{R}^{n}$.

$\endgroup$
  • 1
    $\begingroup$ Given the motivation, why do we want to compute eigenvalues? Since the matrix isn't symmetric, eigenvalues don't relate to the stability of the computation, and you don't want to iterate the computation. $\endgroup$ – David E Speyer Jul 9 '14 at 16:34
  • $\begingroup$ @David Speyer, The main problem is support function estimation, i. e. recovering the convex body from the measurements of its support function. It seems to me that such problem can be solved directly without using iterative methods, such as least squares method is solved. Yes, you will say that such problem is more complex that least squares... but... $\endgroup$ – Ilya Palachev Jul 9 '14 at 16:41
  • 1
    $\begingroup$ I am surprised: you find an eigenvector which isn't one for in the circulant case, comparing with wikipedia? $\endgroup$ – username Jul 15 '14 at 20:12
  • $\begingroup$ @Athanagor Wurlitzer, do you mean $v_{2} = (0, \sin(\theta_{1}), \ldots, \sin(\theta_{M - 1}))^{T}$ ? It is the imaginatory part of the eigenvector $(1, \omega_{j}, \omega_{j}^{2}, \ldots, \omega_{j}^{M - 1})$, where $\omega_{j} = exp(\frac{2 \pi i j}{M})$ for $j = 1$. $\endgroup$ – Ilya Palachev Jul 16 '14 at 9:21
5
$\begingroup$

If no further constraints are imposed on the $\theta_k$, there seems to be no simple form for the eigenvalues( other than $0$, which has multiplicity $\geq 2$ as explained in the OP). Indeed, I show an example below where the nonzero eigenvalues are not expressible by radicals.

Let $M=7$, and choose the following values for the $\theta_k$ (note that they are between $\frac{\pi}{4}$ and $\frac{\pi}{2}$).

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \cos(\theta_k) & \frac{20}{29} & \frac{65}{97} & \frac{48}{73} & \frac{3}{5} & \frac{28}{53} & \frac{33}{65} & \frac{8}{17} \\ \hline \sin(\theta_k) & \frac{21}{29} & \frac{72}{97} & \frac{55}{73} & \frac{4}{5} & \frac{45}{53} & \frac{56}{65} & \frac{15}{17} \\ \hline \end{array} $$

Then we have

$$ C=\left(\begin{array}{ccccccc} \frac{-399}{1649} & \frac{132}{493} & 0 & 0 & 0 & 0 & \frac{75}{2813} \\ \frac{-119}{7081} & \frac{92}{2117} & \frac{-75}{2813} & 0 & 0 & 0 & 0 \\ 0 & \frac{-27}{365} & \frac{44}{485} & \frac{-119}{7081} & 0 & 0 & 0 \\ 0 & 0 & \frac{-23}{265} & \frac{620}{3869} & \frac{-27}{365} & 0 & 0 \\ 0 & 0 & 0 & \frac{-83}{3445} & \frac{36}{325} & \frac{-23}{265} & 0 \\ 0 & 0 & 0 & 0 & \frac{-47}{1105} & \frac{60}{901} & \frac{-83}{3445} \\ \frac{-47}{1105} & 0 & 0 & 0 & 0 & \frac{132}{493} & \frac{-427}{1885} \\ \end{array}\right) $$

The characteristic polynomial of $C$ is $\chi_C=X^2P$, where $$ P=x^5 - \frac{198395974}{60131320925}x^4 - \frac{58043714683396506772}{723155151237068571125}x^3 + \frac{12655356459504058576}{3615775756185342855625}x^2 + \frac{1065764359163841911}{723155151237068571125}x - \frac{186332188794386}{1701541532322514285} $$

And PARI-GP tells us that this polynomial is irreducible and has Galois group ${\mathfrak S}_5$, which is not solvable. So the roots of $P$ are not expressible by radicals.

$\endgroup$
  • $\begingroup$ Hello! Does it mean that we cannot obtain roots expressed by sines and cosines, as the one described above? Your counter-example shows only that roots are not expressible by radicals, but does it show that they are not expressible as, for example sines and cosines? $\endgroup$ – Ilya Palachev Nov 1 '18 at 18:07
  • $\begingroup$ @IlyaPalachev Can you make your question more precise : sines and cosines of what ? (I mean, any number in $[-1,1]$ is a sine or cosine or something). $\endgroup$ – Ewan Delanoy Nov 1 '18 at 18:17
  • $\begingroup$ I mean that already known eigenvector $(1, \cos(\theta_{1}), \ldots, \cos(\theta_{M - 1}))^{T}$ has coordinates that, generally speaking, in most cases cannot be represented in radicals. But they can be simply written as the result of composition of elementary functions on $\theta_i$. $\endgroup$ – Ilya Palachev Nov 6 '18 at 12:49
  • $\begingroup$ So it's still not proved that other eigenvectors and eigenvalues cannot be represented in some way like that one. $\endgroup$ – Ilya Palachev Nov 6 '18 at 12:51
  • 1
    $\begingroup$ @IlyaPalachev A consequence of my counterexample is that the non-zero eigenvalues cannot be rational functions in the $\cos(\theta_k)$ and $\sin(\theta_k)$. It might still be possible of course that they be rational functions of $\cos(\frac{\theta_k}{d})$ and $\sin(\frac{\theta_k}{d})$ for some suitable integer denominator $d$. $\endgroup$ – Ewan Delanoy Nov 6 '18 at 16:03

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.