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$
4
  • 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$ Jul 9, 2014 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$ Jul 9, 2014 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$
    – user145413
    Jul 15, 2014 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$ Jul 16, 2014 at 9:21

1 Answer 1

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$
6
  • $\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$ Nov 1, 2018 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$ Nov 1, 2018 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$ Nov 6, 2018 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$ Nov 6, 2018 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$ Nov 6, 2018 at 16:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .