# Eigenvalues of Symmetric Non-normalized
Discrete Trigonometric Transforms

Ali Bagheri Bardi, Miloš Daković , Taher Yazdanpanah, Ljubiša Stanković A.
Bagheri-Bardi<EMAIL_ADDRESS>is with Persian Gulf University, Bushehr,
Iran, on sabbatical leave at the University of MontenegroT. Yazdanpanah
<EMAIL_ADDRESS>is with Persian Gulf University, Bushehr, IranM.
Daković<EMAIL_ADDRESS>and L. Stanković<EMAIL_ADDRESS>are with
University of Montenegro, Faculty of Electrical Engineering, Podgorica,
Montenegro. This paper is submitted to an IEEE journal.

###### Abstract

A comprehensive approach to the spectrum characterization (derivation of
eigenvalues and the corresponding multiplicities) for non-normalized,
symmetric discrete trigonometric transforms (DTT) is presented in the paper.
Eight types of the DTT are analyzed. New explicit analytic expressions for the
eigenvalues, together with their multiplicities, for the cases of three DTT
(DCT(1), DCT(5), and DST(8)), are the main contribution of this paper.
Moreover, the presented theory is supplemented by new, original derivations
for the closed-form expressions of the square and the trace of analyzed DTT
matrices.

###### Index Terms:

Discrete trigonometric transforms, Discrete cosine transforms, Discrete sine
transforms, eigenvalues

##  I Introduction

Discrete Trigonometric Transforms (DTT) are irreplaceable tools in signal and
image processing applications. There exist 16 types of the DTT [1, 2, 3, 4, 5,
6, 7, 8, 9] divided into two classes: Discrete Cosine Transforms (DCT) and
Discrete Sine Transforms (DST). In each class, eight types of these transforms
are defined. In addition, there are non-normalized and normalized variants of
the DTT. All of these transforms are linear, and therefore, for a given signal
of length $n$, they can be suitably represented using $n\times n$
transformation matrices.

Herein, we will focus on the symmetric non-normalized DTT, that is, on the DST
of type 1, 4, 5, and 8 and the DCT of type 1, 4, 5, and 8. The elements of the
transformation matrix for each analyzed DTT are given in Table I, where
$k=0,1,\ldots,n-1$ is a row index and $l=0,1,\ldots,n-1$ is a column index.
The DTT of type $m$ are denoted as DCT(m) and DST(m), and the corresponding
transformation matrices are denoted as $\mathbf{C}_{(m)}$ and
$\mathbf{S}_{(m)}$.

Eigenvalues of the DTT are studied in [10, 11, 12, 13, 15, 16, 14]. However,
analytic results are provided only for 5 types of symmetric non-normalized
DTT, covering the cases when the square of the transformation matrix
$\mathbf{A}$ is proportional to the identity matrix,
$\mathbf{A}^{2}=\lambda\mathbf{I}$.

Eigendecompositions of the DST(4) and the DCT(4) are analyzed in [10].
Therein, the authors use the Generalized Discrete Fourier Transform (GDFT),
and the theory of commuting matrices in order to obtain approximate
eigendecompositions of DST(4) and DCT(4). In [11] it has been shown that the
DCT(1) and DST(1) eigenvectors can be attained from the DFT eigenvectors. The
offset Discrete Fourier Transform (DFT) is used in [12], where it has been
shown that an even-order DCT(4), DST(4), and DST(8) can be viewed as a special
case of an even-order offset DFT. This approach has led to the eigenvalues
(and their corresponding multiplicities) for these three types of DTT. The
approach based on commuting matrices is used in [14, 15] to determine the
eigenvectors of some DTT. Non-symmetric DTT are analyzed in [16], providing a
conjecture that all eigenvalues are distinct for non-symmetric DTT of
arbitrary order.

Our aim is to find the eigenvalues, with their corresponding multiplicities,
in an analytic way, for each considered DTT. Applying some well-known
trigonometric identities, we directly obtain the square and the trace of all
eight types of DTT matrices. We observe that the square of the transformation
matrix for three types of non-normalized DTT, (the DCT(1), DCT(5), and DST(8))
is not a multiple of the identity matrix. Using the formula for the trace, we
compute the multiplicity of the eigenvalues in all considered cases.

Herein, we develop a unified analytic approach to DTT eigenvalues (and
corresponding multiplicities), containing novel results for the DCT(1),
DCT(5), and DST(8). Mathematically relevant expressions for the square and the
trace of the analyzed DTT matrices arise as intermediate results, that are
used for the calculation of the eigenvalues and their corresponding
multiplicities.

TABLE I: Definitions for symmetric, non-normalized DTT Type | $\left(s_{kl}\right)_{k,l=0}^{n-1}$ |  | Type | $\left(c_{kl}\right)_{k,l=0}^{n-1}$
---|---|---|---|---
DST(1) | $\sin\frac{(k+1)(l+1)\pi}{n+1}$ |  | DCT(1) | $\cos\frac{kl\pi}{n-1}$
DST(4) | $\sin\frac{(2k+1)(2l+1)\pi}{4n}$ |  | DCT(4) | $\cos\frac{(2k+1)(2l+1)\pi}{4n}$
DST(5) | $\sin\frac{2(k+1)(l+1)\pi}{2n+1}$ |  | DCT(5) | $\cos\frac{2kl\pi}{2n-1}$
DST(8) | $\sin\frac{(2k+1)(2l+1)\pi}{4n-2}$ |  | DCT(8) | $\cos\frac{(2k+1)(2l+1)\pi}{4n+2}$

The main results are summarized in Section II. Squares of DTT matrices are
evaluated in Section III while their traces are derived in Section IV. In
Section V, the analytic proofs for the results presented in Section II are
presented.

##  II Results

The eigenvalues along with their corresponding multiplicities, for the
considered types of DTT are presented in Tables II and III. These expressions
are the main result of this paper.

By carefully observing these forms, we can see that five DTT types have only
two distinct eigenvalues and that for an odd $n$, in each case, the
multiplicity of the positive eigenvalue is greater by one than the
multiplicity of the corresponding negative eigenvalue.

TABLE II: Eigenvalues and corresponding multiplicities DTT type | Eigenvalue | Multiplicity
---|---|---
even $n$ | odd $n$
DCT(4), DST(4) | $\lambda_{1}=-\sqrt{\dfrac{n}{2}}$ | $\dfrac{n}{2}$ | $\dfrac{n-1}{2}$
$\lambda_{2}=\sqrt{\dfrac{n}{2}}$ | $\dfrac{n}{2}$ | $\dfrac{n+1}{2}$
DCT(8), DST(5) | $\lambda_{1}=-\sqrt{\dfrac{2n+1}{4}}$ | $\dfrac{n}{2}$ | $\dfrac{n-1}{2}$
$\lambda_{2}=\sqrt{\dfrac{2n+1}{4}}$ | $\dfrac{n}{2}$ | $\dfrac{n+1}{2}$
DST(1) | $\lambda_{1}=-\sqrt{\dfrac{n+1}{2}}$ | $\dfrac{n}{2}$ | $\dfrac{n-1}{2}$
$\lambda_{2}=\sqrt{\dfrac{n+1}{2}}$ | $\dfrac{n}{2}$ | $\dfrac{n+1}{2}$
| $\lambda_{1}=\dfrac{1}{4}-\sqrt{n-\dfrac{7}{16}}$ | $1$ | $1$
DCT(5) | $\lambda_{2}=-\sqrt{\dfrac{2n-1}{4}}$ | $\dfrac{n}{2}-1$ | $\dfrac{n-3}{2}$
$\lambda_{3}=\sqrt{\dfrac{2n-1}{4}}$ | $\dfrac{n}{2}-1$ | $\dfrac{n-1}{2}$
| $\lambda_{4}=\dfrac{1}{4}+\sqrt{n-\dfrac{7}{16}}$ | $1$ | $1$
| $\lambda_{1}=-\dfrac{(-1)^{n}}{4}-\sqrt{n-\dfrac{7}{16}}$ | $1$ | $1$
DST(8) | $\lambda_{2}=-\sqrt{\dfrac{2n-1}{4}}$ | $\dfrac{n}{2}-1$ | $\dfrac{n-3}{2}$
$\lambda_{3}=\sqrt{\dfrac{2n-1}{4}}$ | $\dfrac{n}{2}-1$ | $\dfrac{n-1}{2}$
| $\lambda_{4}=-\dfrac{(-1)^{n}}{4}+\sqrt{n-\dfrac{7}{16}}$ | $1$ | $1$

For the DCT of type 5 and the DST of type 8 there are four eigenvalues. Two of
them have multiplicity one, and the multiplicities of other two eigenvalues
are equal in the case of even $n$, or differ by one in the case of odd $n$,
where again the positive eigenvalue has greater multiplicity.

The most complicated case is the DCT of type 1, where there are six distinct
eigenvalues. Four of them have multiplicity one and the remaining two
eigenvalues have equal multiplicities (for even $n$), whereas the positive
eigenvalue multiplicity is greater by one than the negative eigenvalue
multiplicity (for odd $n$ case).

In the following section, we provide detailed discussion, derivations and
proofs for the presented results.

TABLE III: DCT type 1 eigenvalues odd $n$ | even $n$
---|---
Eigenvalue | Mult. | Eigenvalue | Mult.
$\lambda_{1}=-\sqrt{n-1}$ | $1$ | $\lambda_{1}=-\dfrac{\sqrt{2}}{4}-\sqrt{n-\dfrac{7}{8}}$ | 1
$\lambda_{2}=\dfrac{1}{2}-\sqrt{n-\dfrac{3}{4}}$ | $1$ | $\lambda_{2}=\dfrac{\sqrt{2}}{4}-\sqrt{n-\dfrac{7}{8}}$ | 1
$\lambda_{3}=-\sqrt{\dfrac{n-1}{2}}$ | $\dfrac{n-5}{2}$ | $\lambda_{3}=-\sqrt{\dfrac{n-1}{2}}$ | $\dfrac{n}{2}-2$
$\lambda_{4}=\sqrt{\dfrac{n-1}{2}}$ | $\dfrac{n-3}{2}$ | $\lambda_{4}=\sqrt{\dfrac{n-1}{2}}$ | $\dfrac{n}{2}-2$
$\lambda_{5}=\sqrt{n-1}$ | $1$ | $\lambda_{5}=-\dfrac{\sqrt{2}}{4}+\sqrt{n-\dfrac{7}{8}}$ | 1
$\lambda_{6}=\dfrac{1}{2}+\sqrt{n-\dfrac{3}{4}}$ | $1$ | $\lambda_{6}=\dfrac{\sqrt{2}}{4}+\sqrt{n-\dfrac{7}{8}}$ | 1

##  III Square of transformation matrix

In order to compute entries $t_{kl}$ of the square of a DTT matrix, we need to
apply some well-known trigonometric identities [17, p.37].

Lagrange’s trigonometric identity states that for $\theta\neq 2k\pi$, where
$k$ is an integer, holds

$\sum_{m=0}^{n}\cos
m\theta=\frac{1}{2}+\frac{\sin(n+\frac{1}{2})\theta}{2\sin\frac{\theta}{2}}.$

Using this identity for $\theta=(a\pi)/n$, where $a$ is an integer that is not
divisible with $2n$, and for $\theta=(2b\pi)/(2n+1)$, where $b$ is an integer
not divisible with $2n+1$ , we get the following two identities

$\displaystyle\sum_{m=0}^{n}\cos\frac{ma\pi}{n}=\frac{1+(-1)^{a}}{2}=\begin{cases}0&\text{for
odd }a\\\ 1&\text{for even }a\end{cases}$ (1)
$\displaystyle\sum_{m=0}^{n}\cos\frac{2mb\pi}{2n+1}=\frac{1}{2}.$ (2)

For an integer $a$ not divisible by $2n$, the following identity holds:

$\sum_{m=0}^{n-1}\cos\frac{(2m+1)a\pi}{2n}=0.$ (3)

For an integer $a$ not divisible by $2n+1$,

$\sum_{m=0}^{n-1}\cos\frac{(2m+1)a\pi}{2n+1}=\frac{(-1)^{a+1}}{2}$ (4)

holds, while for an integer $a$ not divisible by $2n+2$, we have

$\sum_{m=1}^{n}\cos\frac{ma\pi}{n+1}=-\frac{(-1)^{a}+1}{2}=\begin{cases}0&\text{for
odd }a\\\ -1&\text{for even }a.\end{cases}$ (5)

Furthermore, for an integer $a$ not divisible by $2n+1$, we have the
following:

$\sum_{m=0}^{n-1}\cos\frac{2(m+1)a\pi}{2n+1}=-\frac{1}{2}.$ (6)

###  III-A DCT type 1 case

Elements of the squared transformation matrix are

$\displaystyle t_{kl}$
$\displaystyle=\sum_{m=0}^{n-1}\cos\frac{km\pi}{n-1}\cos\frac{ml\pi}{n-1}$
$\displaystyle=\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{m(k+l)\pi}{n-1}+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{m(k-l)\pi}{n-1}.$

Using (1), for $k\neq l$, we further get

$t_{kl}=\frac{1+(-1)^{k+l}}{2}=\begin{cases}0&\text{for odd }k+l\\\
1&\text{for even }k+l.\end{cases}$

For $k=l$, we obtain

$t_{kk}=\begin{cases}\frac{n+1}{2}&\text{for }k=1,2,\ldots,n-2\\\ n&\text{for
}k=0\text{ or }k=n-1.\end{cases}$

###  III-B DCT type 4 case

In this case, the elements of the squared transformation matrix are

$\displaystyle t_{kl}={}$
$\displaystyle\sum_{m=0}^{n-1}\cos\frac{(2k+1)(2m+1)\pi}{4n}\cos\frac{(2m+1)(2l+1)\pi}{4n}$
$\displaystyle={}$
$\displaystyle\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k+l+1)\pi}{2n}$
$\displaystyle+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k-l)\pi}{2n}.$

For $k\neq l$, using (3), we get $t_{kl}=0$. For $k=l$, using (3) for the
first sum only we have

$t_{kk}=\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(2k+1)\pi}{2n}+\frac{n}{2}=\frac{n}{2}.$

###  III-C DCT type 5 case

For this type of the transform we have

$\displaystyle t_{kl}={}$
$\displaystyle\sum_{m=0}^{n-1}\cos\frac{2km\pi}{2n-1}\cos\frac{2ml\pi}{2n-1}$
$\displaystyle={}$
$\displaystyle\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{2m(k+l)\pi}{2n-1}+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{2m(k-l)\pi}{2n-1}.$

For $k\neq l$ using (2) we obtain $t_{kl}=1/2$, while for $k=l$ we get

$t_{kk}=\begin{cases}\frac{2n+1}{4}&\text{for }k\neq 0\\\ n&\text{for
}k=0.\end{cases}$

###  III-D DCT type 8 case

The squared transformation matrix elements for the DCT(8) are given by

$\displaystyle t_{kl}={}$
$\displaystyle\sum_{m=0}^{n-1}\cos\frac{(2k+1)(2m+1)\pi}{4n+2}\cos\frac{(2m+1)(2l+1)\pi}{4n+2}$
$\displaystyle={}$
$\displaystyle\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k+l+1)\pi}{2n+1}$
$\displaystyle+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k-l)\pi}{2n+1}.$

For $k\neq l$, using (4) we get $t_{kl}=0$. Otherwise, for $k=l$, using (4)
for the first sum, we get

$t_{kk}=\frac{1}{4}+\frac{n}{2}=\frac{2n+1}{4}.$

###  III-E DST type 1 case

In the case of DST(1), the elements of the transformation matrix are given by

$\displaystyle t_{kl}={}$
$\displaystyle\sum_{m=0}^{n-1}\sin\frac{(k+1)(m+1)\pi}{n+1}\sin\frac{(m+1)(l+1)\pi}{n+1}$
$\displaystyle={}$
$\displaystyle-\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(m+1)(k+l+2)\pi}{n+1}$
$\displaystyle+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(m+1)(k-l)\pi}{n+1}.$

For $k\neq l$, using (5), we have $t_{kl}=0$, while for $k=l$,
$t_{kk}=(n+1)/2$ holds.

###  III-F DST type 4 case

The elements of the squared DST(4) transformation matrix are

$\displaystyle t_{kl}={}$
$\displaystyle\sum_{m=0}^{n-1}\sin\frac{(2k+1)(2m+1)\pi}{4n}\sin\frac{(2m+1)(2l+1)\pi}{4n}$
$\displaystyle={}$
$\displaystyle-\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k+l+1)\pi}{2n}$
$\displaystyle+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k-l)\pi}{2n}.$

For $k\neq l$, using (3) we have $t_{kl}=0$, and for $k=l$ we get
$t_{kk}=n/2$.

###  III-G DST type 5 case

Next, we consider the elements of the squared DST(5) transformation matrix.
These elements are given by

$\displaystyle t_{kl}={}$
$\displaystyle\sum_{m=0}^{n-1}\sin\frac{2(k+1)(m+1)\pi}{2n+1}\sin\frac{2(m+1)(l+1)\pi}{2n+1}$
$\displaystyle={}$
$\displaystyle-\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{2(m+1)(k+l+2)\pi}{2n+1}$
$\displaystyle+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{2(m+1)(k-l)\pi}{2n+1}.$

For $k\neq l$, using (6) we have $t_{kl}=0$, and for $k=l$ we get
$t_{kk}=(2n+1)/4$.

###  III-H DST type 8 case

For the DST(8) the elements of squared matrix are

$\displaystyle t_{kl}={}$
$\displaystyle\sum_{m=0}^{n-1}\sin\frac{(2k+1)(2m+1)\pi}{4n-2}\sin\frac{(2m+1)(2l+1)\pi}{4n-2}$
$\displaystyle={}$
$\displaystyle-\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k+l+1)\pi}{2n-1}$
$\displaystyle+\frac{1}{2}\sum_{m=0}^{n-1}\cos\frac{(2m+1)(k-l)\pi}{2n-1}.$

In this case, for $k\neq l$, using (4) we get $t_{kl}=(-1)^{k+l}/2$, whereas
for $k=l$ we have

$t_{kk}=\begin{cases}\frac{2n+1}{4}&\text{for }k=0,1,\ldots,n-2\\\ n&\text{for
}k=n-1.\end{cases}$

##  IV Trace of transformation matrix

In this section, we will determine the trace for each of the previous
transformation matrices. To this aim, we use the following identities

$\sum_{k=0}^{m-1}\cos\frac{2k^{2}\pi}{m}=\frac{\sqrt{m}}{2}\left(1+\cos\frac{m\pi}{2}+\sin\frac{m\pi}{2}\right)$
(7)
$\sum_{k=0}^{m-1}\sin\frac{2k^{2}\pi}{m}=\frac{\sqrt{m}}{2}\left(1+\cos\frac{m\pi}{2}-\sin\frac{m\pi}{2}\right).$
(8)

For the DCT(1), DCT(4), DST(1), and DST(4), for an even number, $n$, the
diagonal elements, $d_{k}$, of transformation matrix are anti-symmetric, that
is, $d_{k}=-d_{n-1-k}$. The trace of these matrices is obviously zero (for an
even $n$),

$\operatorname{Tr}{\mathbf{C}_{(1)}}=\operatorname{Tr}{\mathbf{C}_{(4)}}=\operatorname{Tr}{\mathbf{S}_{(1)}}=\operatorname{Tr}{\mathbf{S}_{(4)}}=0,\
\text{for even }n.$ (9)

Next, we derive the value of the transformation matrix trace in other cases.

###  IV-A DCT type 1, odd $n$ case

From (7), using $m=2(n-1)$, we get

$\displaystyle\sqrt{2(n-1)}$
$\displaystyle=\sum_{k=0}^{2n-3}\cos\frac{k^{2}\pi}{n-1}$
$\displaystyle=\sum_{k=0}^{n-2}\cos\frac{k^{2}\pi}{n-1}+\sum_{k=0}^{n-2}\cos\frac{(k+n-1)^{2}\pi}{n-1}$
$\displaystyle=2\sum_{k=0}^{n-2}\cos\frac{k^{2}\pi}{n-1}=2\sum_{k=0}^{n-1}\cos\frac{k^{2}\pi}{n-1}-2.$

Previous result is the basis for the explicit expression for the trace of the
DCT type 1, $\mathbf{C}_{(1)}$, given as follows

$\operatorname{Tr}{\mathbf{C}_{(1)}}=\sum_{k=0}^{n-1}\cos\frac{k^{2}\pi}{n-1}=\begin{cases}0&\text{for
even }n\\\ \frac{2+\sqrt{2n-2}}{2}&\text{for odd }n.\end{cases}$ (10)

###  IV-B DCT type 4, odd $n$ case

Substituting $m=8n$ in (7) we get

$\displaystyle 2\sqrt{2n}$
$\displaystyle=\sum_{k=0}^{8n-1}\cos\frac{k^{2}\pi}{4n}$
$\displaystyle=\sum_{k=0}^{4n-1}\cos\frac{k^{2}\pi}{4n}+\sum_{k=0}^{4n-1}\cos\frac{(k+4n)^{2}\pi}{4n}$
$\displaystyle=2\sum_{k=0}^{4n-1}\cos\frac{k^{2}\pi}{4n}$
$\displaystyle=2\sum_{k=0}^{2n-1}\cos\frac{k^{2}\pi}{n}+2\sum_{k=0}^{2n-1}\cos\frac{(2k+1)^{2}\pi}{4n}.$

The first sum follows from (7) when we put $m=2n$, and since $n$ is odd it is
equal to zero. Let us decompose the second sum as

$\displaystyle 2\sqrt{2n}=$
$\displaystyle{}2\sum_{k=0}^{n-1}\cos\frac{(2k+1)^{2}\pi}{4n}+2\sum_{k=0}^{n-1}\cos\frac{(2n+2k+1)^{2}\pi}{4n}$
$\displaystyle={}$
$\displaystyle{}4\sum_{k=0}^{n-1}\cos\frac{(2k+1)^{2}\pi}{4n}.$

Now we get the trace for this transformation matrix as

$\operatorname{Tr}{\mathbf{C}_{(4)}}=\sum_{k=0}^{n-1}\cos\frac{(2k+1)^{2}\pi}{4n}=\begin{cases}0&\text{for
even }n\\\ \sqrt{\frac{n}{2}}&\text{for odd }n.\end{cases}$ (11)

###  IV-C DCT type 5 case

For the DCT(5) we can use (7), with $m=2n-1$, to obtain

$\displaystyle\frac{\sqrt{2n-1}}{2}(1+(-1)^{n})=\sum_{k=0}^{2n-2}\cos\frac{2k^{2}\pi}{2n-1}$
$\displaystyle=\sum_{k=0}^{n-1}\cos\frac{2k^{2}\pi}{2n-1}+\sum_{k=0}^{n-2}\cos\frac{2(2n-2-k)^{2}\pi}{2n-1}$
$\displaystyle=\sum_{k=0}^{n-1}\cos\frac{2k^{2}\pi}{2n-1}+\sum_{k=0}^{n-2}\cos\frac{2(k+1)^{2}\pi}{2n-1}$
$\displaystyle=2\sum_{k=0}^{n-1}\cos\frac{2k^{2}\pi}{2n-1}-1.$

Finally, the trace of $\mathbf{C}_{(5)}$ is given as

$\operatorname{Tr}{\mathbf{C}_{(5)}}=\sum_{k=0}^{n-1}\cos\frac{2k^{2}\pi}{2n-1}=\begin{cases}\frac{1}{2}&\text{for
even }n\\\ \frac{1+\sqrt{2n-1}}{2}&\text{for odd }n.\end{cases}$ (12)

###  IV-D DCT type 8 case

For the DCT(8) we can set $m=8n+4$ into (7), further leading to

$\displaystyle\sqrt{8n+4}$
$\displaystyle=\sum_{k=0}^{8n+3}\cos\frac{k^{2}\pi}{4n+2}$
$\displaystyle=\sum_{k=0}^{4n+1}\cos\frac{k^{2}\pi}{4n+2}+\sum_{k=0}^{4n+1}\cos\frac{(k+4n+2)^{2}\pi}{4n+2}$
$\displaystyle=2\sum_{k=0}^{4n+1}\cos\frac{k^{2}\pi}{4n+2}$
$\displaystyle=2\sum_{k=0}^{2n}\cos\frac{2k^{2}\pi}{2n+1}+2\sum_{k=0}^{2n}\cos\frac{(2k+1)^{2}\pi}{4n+2}$
$\displaystyle=2\sum_{k=0}^{2n}\cos\frac{2k^{2}\pi}{2n+1}+2\sum_{k=0}^{n-1}\cos\frac{(2k+1)^{2}\pi}{4n+2}$
$\displaystyle\quad+2\sum_{k=0}^{n}\cos\frac{(2(k+n)+1)^{2}\pi}{4n+2}.$

The first sum is equal to

$\sum_{k=0}^{2n}\cos\frac{2k^{2}\pi}{2n+1}=\frac{\sqrt{2n+1}}{2}(1+(-1)^{n}),$

according to (7) with $m=2n+1$.

We have that the third sum can be written as

$\displaystyle\sum_{k=0}^{n}\cos\frac{(2(k+n)+1)^{2}\pi}{4n+2}=\sum_{k=0}^{n}\cos\left(\frac{2k^{2}\pi}{2n+1}+\frac{2n+1}{2}\pi\right)$
$\displaystyle=(-1)^{n+1}\sum_{k=0}^{n}\sin\frac{2k^{2}\pi}{2n+1}.$

From (8), using $m=2n+1$, we get

$\displaystyle\frac{\sqrt{2n+1}}{2}(1-(-1)^{n})=\sum_{k=0}^{2n}\sin\frac{2k^{2}\pi}{2n+1}$
$\displaystyle=\sum_{k=0}^{n}\sin\frac{2k^{2}\pi}{2n+1}+\sum_{k=0}^{n-1}\sin\frac{2(2n-k)^{2}\pi}{2n+1}$
$\displaystyle=\sum_{k=0}^{n}\sin\frac{2k^{2}\pi}{2n+1}+\sum_{k=0}^{n-1}\sin\frac{2(k+1)^{2}\pi}{2n+1}=2\sum_{k=0}^{n}\sin\frac{2k^{2}\pi}{2n+1}.$

Now we have

$\displaystyle\sqrt{8n+4}=\sqrt{2n+1}(1+(-1)^{n})$
$\displaystyle+2\sum_{k=0}^{n-1}\cos\frac{(2k+1)^{2}\pi}{4n+2}+\frac{\sqrt{2n+1}}{2}(1-(-1)^{n})$

or

$\displaystyle\sum_{k=0}^{n-1}\cos\frac{(2k+1)^{2}\pi}{4n+2}=\frac{\sqrt{2n+1}}{4}(1-(-1)^{n})$

resulting in the trace of the DCT(8) of the form

$\operatorname{Tr}{\mathbf{C}_{(8)}}=\sum_{k=0}^{n-1}\cos\frac{(2k+1)^{2}\pi}{4n+2}=\begin{cases}0&\\!\\!\text{for
even }n\\\ \frac{\sqrt{2n+1}}{2}&\\!\\!\text{for odd }n.\end{cases}$ (13)

###  IV-E DST type 1, odd $n$ case

Using $m=2(n+1)$ in 8 we get

$\displaystyle\sqrt{2(n+1)}$
$\displaystyle=\sum_{k=0}^{2n+1}\sin\frac{k^{2}\pi}{n+1}=\sum_{k=0}^{2n}\sin\frac{(k+1)^{2}\pi}{n+1}$
$\displaystyle=\sum_{k=0}^{n-1}\sin\frac{(k+1)^{2}\pi}{n+1}+\sum_{k=0}^{n}\sin\frac{(n+1+k)^{2}\pi}{n+1}$
$\displaystyle=\sum_{k=0}^{n-1}\sin\frac{(k+1)^{2}\pi}{n+1}+\sum_{k=0}^{n}\sin\frac{k^{2}\pi}{n+1}$
$\displaystyle=\sum_{k=0}^{n-1}\sin\frac{(k+1)^{2}\pi}{n+1}+\sum_{k=0}^{n-1}\sin\frac{(k+1)^{2}\pi}{n+1}$
$\displaystyle=2\sum_{k=0}^{n-1}\sin\frac{(k+1)^{2}\pi}{n+1}.$

The trace of this transformation matrix is then

$\operatorname{Tr}{\mathbf{S}_{(1)}}=\sum_{k=0}^{n-1}\sin\frac{(k+1)^{2}\pi}{n+1}=\begin{cases}0&\text{for
even }n\\\ \sqrt{\frac{n+1}{2}}&\text{for odd }n.\end{cases}$ (14)

###  IV-F DST type 4, odd $n$ case

Let start from (8) with $m=8n$, to get

$\displaystyle 2\sqrt{2n}$
$\displaystyle=\sum_{k=0}^{8n-1}\sin\frac{k^{2}\pi}{4n}$
$\displaystyle=\sum_{k=0}^{4n-1}\sin\frac{k^{2}\pi}{4n}+\sum_{k=0}^{4n-1}\sin\frac{(4n+k)^{2}\pi}{4n}$
$\displaystyle=2\sum_{k=0}^{4n-1}\sin\frac{k^{2}\pi}{4n}$
$\displaystyle=2\sum_{k=0}^{2n-1}\sin\frac{2k^{2}\pi}{2n}+2\sum_{k=0}^{2n-1}\sin\frac{(2k+1)^{2}\pi}{4n}.$

Using (8) with $m=2n$ and having in mind that $n$ is odd, we have

$\displaystyle 2\sqrt{2n}$
$\displaystyle=2\sum_{k=0}^{2n-1}\sin\frac{(2k+1)^{2}\pi}{4n}$
$\displaystyle=2\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n}+2\sum_{k=0}^{n-1}\sin\frac{(2n+2k+1)^{2}\pi}{4n}$
$\displaystyle=4\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n}.$

Now we get the trace of DST(4) as

$\operatorname{Tr}{\mathbf{S}_{(4)}}=\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n}=\begin{cases}0&\text{for
even }n\\\ \sqrt{\frac{n}{2}}&\text{for odd }n.\end{cases}$ (15)

###  IV-G DST type 5 case

Using equation (8) with $m=2n+1$ we can write

$\displaystyle\frac{\sqrt{2n+1}}{2}(1-(-1)^{n})=\sum_{k=0}^{2n}\sin\frac{2k^{2}\pi}{2n+1}$
$\displaystyle=\sum_{k=0}^{2n-1}\sin\frac{2(k+1)^{2}\pi}{2n+1}$
$\displaystyle=\sum_{k=0}^{n-1}\sin\frac{2(k+1)^{2}\pi}{2n+1}+\sum_{k=0}^{n-1}\sin\frac{2(2n-k)^{2}\pi}{2n+1}$
$\displaystyle=2\sum_{k=0}^{n-1}\sin\frac{2(k+1)^{2}\pi}{2n+1}.$

The trace for the DST(5) is now obtained in the following explicit form

$\operatorname{Tr}{\mathbf{S}_{(5)}}=\sum_{k=0}^{n-1}\sin\frac{2(k+1)^{2}\pi}{2n+1}=\begin{cases}0&\\!\\!\text{for
even }n\\\ \frac{\sqrt{2n+1}}{2}&\\!\\!\text{for odd }n.\end{cases}$ (16)

###  IV-H DST type 8

Equation (8), with $m=8n-4$, can be transformed in the following way

$\displaystyle\sqrt{8n-4}$
$\displaystyle=\sum_{k=0}^{8n-5}\sin\frac{k^{2}\pi}{4n-2}$
$\displaystyle=\sum_{k=0}^{4n-3}\sin\frac{k^{2}\pi}{4n-2}+\sum_{k=0}^{4n-3}\sin\frac{(4n-2+k)^{2}\pi}{4n-2}$
$\displaystyle=2\sum_{k=0}^{4n-3}\sin\frac{k^{2}\pi}{4n-2}$
$\displaystyle=2\sum_{k=0}^{2n-2}\sin\frac{2k^{2}\pi}{2n-1}+2\sum_{k=0}^{2n-2}\sin\frac{(2k+1)^{2}\pi}{4n-2}$
$\displaystyle=2\sum_{k=0}^{2n-2}\sin\frac{2k^{2}\pi}{2n-1}+2\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n-2}$
$\displaystyle\quad+2\sum_{k=0}^{n-2}\sin\frac{(2(k+n)+1)^{2}\pi}{4n-2}$
$\displaystyle=2\sum_{k=0}^{2n-2}\sin\frac{2k^{2}\pi}{2n-1}+2\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n-2}$
$\displaystyle\quad-2(-1)^{n}\sum_{k=0}^{n-2}\cos\frac{2(k+1)^{2}\pi}{2n-1}.$

The first sum can be calculated using (8) with $m=2n-1$ as

$2\sum_{k=0}^{2n-2}\sin\frac{2k^{2}\pi}{2n-1}=\sqrt{2n-1}(1+(-1)^{n}).$

The third sum follows from (7) with $m=2n-1$ as

$\displaystyle\frac{\sqrt{2n-1}}{2}(1-(-1)^{n})=\sum_{k=0}^{2n-2}\cos\frac{2k^{2}\pi}{2n-1}$
$\displaystyle=1+\sum_{k=0}^{n-2}\cos\frac{2(k+1)^{2}\pi}{2n-1}+\sum_{k=0}^{n-2}\cos\frac{2(2n-2-k)^{2}\pi}{2n-1}$
$\displaystyle=1+2\sum_{k=0}^{n-2}\cos\frac{2(k+1)^{2}\pi}{2n-1}.$

Now, we can write

$\displaystyle\sqrt{8n-4}=\sqrt{2n-1}(1+(-1)^{n})+2\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n+2}$
$\displaystyle-(-1)^{n}\left(\frac{\sqrt{2n-1}}{2}(1-(-1)^{n})-1\right),$

resulting in

$\displaystyle\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n+2}=\frac{\sqrt{2n-1}}{4}(1-(-1)^{n})-\frac{(-1)^{n}}{2},$

and finally

$\operatorname{Tr}{\mathbf{S}_{(8)}}=\sum_{k=0}^{n-1}\sin\frac{(2k+1)^{2}\pi}{4n-2}=\begin{cases}-\frac{1}{2}&\text{for
even }n\\\ \frac{1+\sqrt{2n-1}}{2}&\text{for odd }n.\end{cases}$ (17)

##  V Proofs for DTT eigenvalues and their multiplicities

Within this section we will use notation $\mathbf{e}_{k}$ for the standard
basis vectors, that is, $\mathbf{e}_{k}$, $k=1,2,\ldots,n$ is the $k$-th
column of $n\times n$ identity matrix.

###  V-A DTT with two eigenvalues

Here we will analyze the DCT of type 4 and 8 and the DST of type 1, 4 and 5.
In all considered cases, according to results presented in Sections III-B,
III-D, III-E, III-F and III-G, square of the transformation matrix is
proportional to the identity matrix $\mathbf{I}$,

$\displaystyle\mathbf{C}_{(4)}^{2}=\mathbf{S}_{(4)}^{2}$
$\displaystyle=\frac{n}{2}\mathbf{I}$
$\displaystyle\mathbf{C}_{(8)}^{2}=\mathbf{S}_{(5)}^{2}$
$\displaystyle=\frac{2n+1}{4}\mathbf{I}$ $\displaystyle\mathbf{S}_{(1)}^{2}$
$\displaystyle=\frac{n+1}{2}\mathbf{I},$

resulting in eigenvalues of the corresponding matrices as in Table II.
Multiplicity of the positive and negative eigenvalue can be determined by
calculating the trace of the transformation matrix. Denote by ${{p}}$ the
multiplicity of positive eigenvalue and by ${{m}}$ the multiplicity of
negative eigenvalue. We know that ${{p}}+{{m}}=n$ and that the trace of the
transformation matrix is $({{p}}-{{m}})\lambda^{+}$, where $\lambda^{+}$ is
the positive eigenvalue.

Using (11), (13), (14), (15), and (16) we can conclude that for even $n$, the
traces of the transformation matrices are equal to zero, meaning that
${{p}}={{m}}=n/2$. For odd $n$ in each case we obtain that the trace of the
transformation matrix is $\lambda^{+}$, meaning that ${{p}}={{m}}+1$, that is,
${{p}}=(n+1)/2$ and ${{m}}=(n-1)/2$.

###  V-B DCT type 5 case

Let us consider the following decomposition of $\mathbb{R}^{n}$

$\displaystyle\mathbb{R}^{n}$
$\displaystyle=\mathcal{V}_{1}\oplus\mathcal{V}_{2},$

where vectors in $\mathcal{V}_{1}$ are of the form

$\mathbf{v}=[0,v_{1},v_{2},\ldots,v_{n-1}]^{T}$

with

$\sum_{k=1}^{n-1}v_{k}=0$

and $\mathcal{V}_{2}$ is a two-dimensional space generated by

$\displaystyle\mathbf{q}_{1}$
$\displaystyle=[1,0,0,\ldots,0]^{T}=\mathbf{e}_{1}$
$\displaystyle\mathbf{q}_{2}$
$\displaystyle=[0,1,1,\ldots,1]^{T}=\sum_{k=2}^{n}\mathbf{e}_{k}.$

The square of the DCT type 5 transform matrix, $\mathbf{C}_{(5)}$, according
to the results presented in Section III-C, can be written as

$\mathbf{C}_{(5)}^{2}=\operatorname{diag}_{n}\left(\frac{2n-1}{2},\frac{2n-1}{4},\ldots,\frac{2n-1}{4}\right)+\frac{1}{2}\mathbf{1}_{n},$
(18)

where $\operatorname{diag}_{n}(\cdot)$ is an $n\times n$ diagonal matrix and
$\mathbf{1}_{n}$ is an $n\times n$ matrix with all ones. It is obvious that
$\mathcal{V}_{1}$ is within null space of $\mathbf{1}_{n}$. Now we have

$\mathbf{C}_{(5)}^{2}\mathbf{v}=\frac{2n-1}{4}\mathbf{v}\qquad(\forall\mathbf{v}\in\mathcal{V}_{1}),$
(19)

meaning that $\frac{2n-1}{4}$ is an eigenvalue of $\mathbf{C}_{(5)}^{2}$. Note
that both of the following matrices

$\mathbf{C}_{(5)}\pm\sqrt{\frac{2n-1}{4}}\mathbf{I}$ (20)

are singular.

If $\mathbf{C}_{(5)}-\sqrt{\frac{2n-1}{4}}\mathbf{I}$ is non-singular, based
on (19), we have

$\mathbf{C}_{(5)}\mathbf{v}=\sqrt{\frac{2n-1}{4}}\mathbf{v}\qquad(\forall\mathbf{v}\in\mathcal{V}_{1}),$

which is impossible. It implies that $\lambda=\pm\sqrt{\frac{2n-1}{4}}$ are
eigenvalues of $\mathbf{C}_{(5)}$. Moreover the sum of the multiplicities is
at least $n-2$. Since $\mathcal{V}_{1}$ is invariant under the symmetric
transform $\mathbf{C}_{(5)}$, the other summand $\mathcal{V}_{2}$ remains
invariant as well. Thus, focusing on $\mathcal{V}_{2}$, we will find the other
eigenvalues. We have that

$\displaystyle\mathbf{C}_{(5)}\mathbf{q}_{1}$
$\displaystyle=\mathbf{q}_{1}+\mathbf{q}_{2}$ (21)
$\displaystyle\mathbf{C}_{(5)}\mathbf{q}_{2}$
$\displaystyle=(n-1)\mathbf{q}_{1}-\frac{1}{2}\mathbf{q}_{2}.$ (22)

The eigenvalues (and the corresponding eigenvectors) can be found by solving

$\mathbf{C}_{(5)}(\mathbf{q}_{1}+x\mathbf{q}_{2})=\lambda(\mathbf{q}_{1}+x\mathbf{q}_{2})$

for unknown $\lambda$ (and $x$). Using (21) and (22) we get

$(x(n-1)+1)\mathbf{q}_{1}+\mathbf{q}_{2}+(1-\frac{x}{2})\mathbf{q}_{2}=\lambda\mathbf{q}_{1}+\lambda
x\mathbf{q}_{2},$

resulting in a system of equations

$\displaystyle x(n-1)+1$ $\displaystyle=\lambda$ $\displaystyle 1-\frac{x}{2}$
$\displaystyle=\lambda x,$

and the eigenvalues

$\lambda=\frac{1}{4}\pm\sqrt{n-\frac{7}{16}},$

each with multiplicity one, as stated in Table II. Therefore, we can conclude
that $\mathbf{C}_{(5)}$ has just four distinct eigenvalues.

Multiplicity of eigenvalues can be determined using the trace of the
transformation matrix (12) and the fact that their multiplicities sum to
$n-2$. The sum of all eigenvalues is

$\frac{1}{2}+({{p}}-{{m}})\sqrt{\frac{2n-1}{4}},$

resulting in ${{p}}={{m}}=n/2$ for an even $n$ and ${{p}}=(n-1)/2$,
${{m}}=(n-3)/2$ for an odd $n$.

###  V-C DST type 8 case

In analogy to the previous case, the subspace $\mathcal{V}_{1}$ is a set of
vectors

$\mathbf{v}=[v_{0},v_{1},v_{2},\ldots,v_{n-2},0]^{T},$

satisfying

$\sum_{k=0}^{n-2}(-1)^{k}v_{k}=0,$

whereas $\mathcal{V}_{2}$ is a two-dimensional space generated by

$\displaystyle\mathbf{q}_{1}$
$\displaystyle=[0,0,\ldots,0,1]^{T}=\mathbf{e}_{n}$
$\displaystyle\mathbf{q}_{2}$
$\displaystyle=[1,-1,1,-1,\ldots,(-1)^{n-2},0]^{T}=-\sum_{k=1}^{n-1}(-1)^{k}\mathbf{e}_{k}.$

The square of $\mathbf{S}_{(8)}$ matrix, according to Section III-H, can be
written as

$\mathbf{S}_{(8)}^{2}=\operatorname{diag}_{n}\left(\frac{2n-1}{4},\frac{2n-1}{4},\cdots,\frac{2n-1}{2}\right)+\frac{1}{2}\mathbf{Q}.$
(23)

The elements of matrix $\mathbf{Q}$ are defined by $q_{kl}=(-1)^{kl}$. Again,
the vector space $\mathcal{V}_{1}$ is within the null space of $\mathbf{Q}$
resulting in

$\mathbf{S}_{(8)}^{2}\mathbf{v}=\frac{2n-1}{4}\mathbf{v}\qquad(\forall\mathbf{v}\in\mathcal{V}_{1}).$

Therefore, $\frac{2n-1}{4}$ is an eigenvalue of $\mathbf{S}_{(8)}^{2}$. One
may conclude that both $\pm\sqrt{\frac{2n-1}{4}}$ are eigenvalues of
$\mathbf{S}_{(8)}$. Moreover, the sum of multiplicities is at least $n-2$.

The other eigenvalues can be found by solving

$\mathbf{S}_{(8)}(\mathbf{q}_{1}+x\mathbf{q}_{2})=\lambda(\mathbf{q}_{1}+x\mathbf{q}_{2}).$

Using

$\displaystyle\mathbf{S}_{(8)}\mathbf{q}_{1}$
$\displaystyle=(-1)^{n-1}\mathbf{q}_{1}+\mathbf{q}_{2}$
$\displaystyle\mathbf{S}_{(8)}\mathbf{q}_{2}$
$\displaystyle=(n-1)\mathbf{q}_{1}+\frac{(-1)^{n}}{2}\mathbf{q}_{2},$

we obtain the system of equations

$\displaystyle(-1)^{n-1}+(n-1)x$ $\displaystyle=\lambda$ $\displaystyle
1+\frac{(-1)^{n}}{2}x$ $\displaystyle=\lambda x$

with solutions

$\lambda=-\frac{(-1)^{n}}{4}\pm\sqrt{n-\frac{7}{16}}.$

Each eigenvalue has multiplicity one.

Now we can determine the multiplicities of all eigenvalues. Denoting by
${{p}}$ the multiplicity of eigenvalue $\sqrt{(2n-1)/{4}}$ and with ${{m}}$
the multiplicity of $-\sqrt{(2n-1)/{4}}$, where ${{p}}+{{m}}=n-2$ we have that
the sum of all eigenvalues is

$({{p}}-{{m}})\sqrt{\frac{2n-1}{4}}-\frac{(-1)^{n}}{2}.$ (24)

This sum is equal to the trace of $\mathbf{S}_{(8)}$ matrix (17). For even $n$
we have that the trace is $-\frac{1}{2}$, meaning that
${{p}}={{m}}=\frac{n-2}{2}$. For an odd $n$ we have that ${{p}}-{{m}}=1$,
resulting in ${{p}}=\frac{n-1}{2}$ and ${{m}}=\frac{n-3}{2}$, as given in
Table II.

###  V-D DCT type 1 case

Similar to the previous types, to get the eigenvalues of $\mathbf{C}_{(1)}$,
we split the problem to some simpler components. In this case, we have to
consider the odd and the even cases separately. Moreover $\mathbb{R}^{n}$ is
decomposed into three orthogonal subspaces,

$\mathbb{R}^{n}=\mathcal{V}_{1}\oplus\mathcal{V}_{2}\oplus\mathcal{V}_{3}.$
(25)

Let $\mathcal{V}_{1}$ be the $(n-4)$-dimensional vector space containing
vectors $\mathbf{v}=[0,v_{1},v_{2},\cdots,v_{n-2},0]^{T}$ such that the sum of
even indexed values is zero and the sum of odd indexed values is also zero

$\sum_{k=1}^{(n-3)/2}v_{2k}=0\quad\text{and}\quad\sum_{k=1}^{(n-1)/2}v_{2k-1}=0.$

Note that, according to Section III-A, we have

$\mathbf{C}_{(1)}^{2}=\operatorname{diag}(n-1,\frac{n-1}{2},\frac{n-1}{2},\cdots,\frac{n-1}{2},n-1)+\mathbf{P},$

where $\mathbf{P}$ is an $n\times n$ matrix with elements

$p_{kl}=\frac{1+(-1)^{k+l}}{2}=\begin{cases}0&\text{ for odd }k+l\\\ 1&\text{
for even }k+l.\end{cases}$

One may directly check that $\mathcal{V}_{1}$ is contained in the null space
of $\mathbf{P}$. Applying this point, we get that

$\mathbf{C}_{(1)}^{2}\mathbf{v}=\frac{n-1}{2}\mathbf{v}\qquad(\forall\mathbf{v}\in\mathcal{V}_{1}).$
(26)

Thus, ${(n-1)}/{2}$ is an eigenvalue of $\mathbf{C}_{(1)}^{2}$. Similar to the
two previous type transforms, we conclude that $\pm\sqrt{(n-1)/2}$ are
eigenvalues of $\mathbf{C}_{(1)}$ corresponding to $\lambda_{3}$ and
$\lambda_{4}$ in Table III for even and odd $n$.

Suppose that $n$ is odd. Let us define the vector space $\mathcal{V}_{2}$ as a
two-dimensional space generated by

$\displaystyle\mathbf{q}_{21}$
$\displaystyle=[1,0,0,\ldots,0,-1]^{T}=\mathbf{e}_{1}-\mathbf{e}_{n}$ (27)
$\displaystyle\mathbf{q}_{22}$
$\displaystyle=[0,1,0,1,0,\ldots,0,1,0]^{T}=\sum_{k=1}^{(n-1)/2}\mathbf{e}_{2k},$
(28)

and $\mathcal{V}_{3}$ as a two-dimensional space generated by

$\displaystyle\mathbf{q}_{31}$
$\displaystyle=[1,0,0,\ldots,0,1]^{T}=\mathbf{e}_{1}+\mathbf{e}_{n}$ (29)
$\displaystyle\mathbf{q}_{32}$
$\displaystyle=[0,0,1,0,1,\ldots,1,0,0]^{T}=\sum_{k=1}^{(n-3)/2}\mathbf{e}_{2k+1}.$
(30)

Consider subspace $\mathcal{V}_{2}$. We have that

$\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{21}$
$\displaystyle=2\mathbf{q}_{22}$ (31)
$\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{22}$
$\displaystyle=\frac{n-1}{2}\mathbf{q}_{21}.$ (32)

Let us now find eigenvalues and eigenvectors within this subspace. We should
find $x$ such that

$\mathbf{C}_{(1)}(\mathbf{q}_{21}+x\mathbf{q}_{22})=\lambda(\mathbf{q}_{21}+x\mathbf{q}_{22})$

for some $\lambda$. Then $\mathbf{q}_{21}+x\mathbf{q}_{22}$ is an eigenvector
in $\mathcal{V}_{2}$ and $\lambda$ is the corresponding eigenvalue. Using (31)
and (32) we get

$2\mathbf{q}_{22}+x\frac{n-1}{2}\mathbf{q}_{21}=\lambda\mathbf{q}_{21}+\lambda
x\mathbf{q}_{22},$

resulting in a system of equations with unknown $x$ and $\lambda$

$\displaystyle 2$ $\displaystyle=\lambda x$ $\displaystyle x\frac{n-1}{2}$
$\displaystyle=\lambda.$

Solutions to this system are the eigenvalues $\lambda=\pm\sqrt{n-1}$
corresponding to $\lambda_{1}$ and $\lambda_{5}$ in Table III for an odd $n$.
Each eigenvalue has multiplicity one.

Consider now $\mathcal{V}_{3}$ space. Similar to the previous case we get

$\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{31}$
$\displaystyle=2\mathbf{q}_{31}+2\mathbf{q}_{32}$
$\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{32}$
$\displaystyle=\frac{n-3}{2}\mathbf{q}_{31}-\mathbf{q}_{31}.$

Next, we search for eigenvectors and eigenvalues from

$\mathbf{C}_{(1)}(\mathbf{q}_{31}+x\mathbf{q}_{32})=\lambda(\mathbf{q}_{31}+x\mathbf{q}_{32}),$

leading to the system of equations

$\displaystyle 2+\frac{n-3}{2}$ $\displaystyle=\lambda$ $\displaystyle 2-x$
$\displaystyle=\lambda x,$

with the solutions

$\lambda=\frac{1}{2}\pm\sqrt{n-\frac{3}{4}},$

corresponding to $\lambda_{2}$ and $\lambda_{6}$ in Table III. Both of the
obtained eigenvalues are with multiplicity one.

Note that in the considered cases we have an analytical form for the
corresponding eigenvectors.

Now we can determine multiplicities of all eigenvalues. Denoting by ${{p}}$
the multiplicity of eigenvalue $\sqrt{(n-1)/{2}}$ and by ${{m}}$ the
multiplicity of $-\sqrt{(n-1)/{2}}$, where ${{p}}+{{m}}=n-4$, we have that the
sum of all eigenvalues is

$({{p}}-{{m}})\sqrt{\frac{n-1}{2}}+1.$ (33)

This sum is equal to the trace of $\mathbf{C}_{(1)}$ matrix (10). We can
conclude that ${{p}}-{{m}}=1$, resulting in ${{p}}=\frac{n-3}{2}$ and
${{m}}=\frac{n-5}{2}$, as given in Table III for odd $n$ case.

Now we will consider the case of an even $n$. In decomposition (25)
$\mathcal{V}_{1}$ remains the same, while $\mathcal{V}_{2}$ is now spanned by
vectors

$\displaystyle\mathbf{q}_{21}$
$\displaystyle=[1,0,0,\ldots,0,\sqrt{2}+1]=\mathbf{e}_{1}+(\sqrt{2}+1)\mathbf{e}_{n}$
(34) $\displaystyle\mathbf{q}_{22}$
$\displaystyle=[0,\sqrt{2}+1,1,\sqrt{2}+1,1,\ldots,\sqrt{2}+1,0]$
$\displaystyle=\sum_{k=2}^{n-1}\mathbf{e}_{k}+\sqrt{2}\sum_{k=1}^{(n-1)/2}\mathbf{e}_{2k}$
(35)

and $\mathcal{V}_{3}$ is spanned by

$\displaystyle\mathbf{q}_{31}$
$\displaystyle=[1,0,0,\ldots,0,-\sqrt{2}-1]=\mathbf{e}_{1}-(\sqrt{2}+1)\mathbf{e}_{n}$
(36) $\displaystyle\mathbf{q}_{32}$
$\displaystyle=[0,1-\sqrt{2},1,1-\sqrt{2},1,\ldots,1-\sqrt{2},0]$
$\displaystyle=\sum_{k=2}^{n-1}\mathbf{e}_{k}-\sqrt{2}\sum_{k=1}^{(n-1)/2}\mathbf{e}_{2k}.$
(37)

It is easy to check that $\mathcal{V}_{2}$ and $\mathcal{V}_{3}$ are invariant
with respect to $\mathbf{C}_{(1)}$, that is,

$\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{21}$
$\displaystyle=\sqrt{2}\mathbf{q}_{21}+(2-\sqrt{2})\mathbf{q}_{22}$ (38)
$\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{22}$
$\displaystyle=(n-2)(1+\frac{\sqrt{2}}{2})\mathbf{q}_{21}-\frac{\sqrt{2}}{2}\mathbf{q}_{22}$
(39) $\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{31}$
$\displaystyle=-\sqrt{2}\mathbf{q}_{31}+(2+\sqrt{2})\mathbf{q}_{32}$ (40)
$\displaystyle\mathbf{C}_{(1)}\mathbf{q}_{32}$
$\displaystyle=-(n-2)\frac{\sqrt{2}}{2}\mathbf{q}_{31}+\frac{\sqrt{2}}{2}\mathbf{q}_{32}.$
(41)

The eigenvalues (with corresponding eigenvectors) can be found by solving the
system

$\displaystyle\mathbf{C}_{(1)}(\mathbf{q}_{21}+x\mathbf{q}_{22})$
$\displaystyle=\lambda(\mathbf{q}_{21}+x\mathbf{q}_{22})$ (42)
$\displaystyle\mathbf{C}_{(1)}(\mathbf{q}_{31}+x\mathbf{q}_{32})$
$\displaystyle=\lambda(\mathbf{q}_{31}+x\mathbf{q}_{32}),$ (43)

for unknown $\lambda$ (and $x$). Form (42), using (38) and (39), we obtain the
system of equations

$\displaystyle\sqrt{2}+x(n-2)(1+\frac{\sqrt{2}}{2})$ $\displaystyle=\lambda$
$\displaystyle 2-\sqrt{2}-x\frac{\sqrt{2}}{2}$ $\displaystyle=\lambda x$

with solutions

$\lambda=\frac{\sqrt{2}}{4}\pm\sqrt{n-\frac{7}{8}},$

corresponding to $\lambda_{2}$ and $\lambda_{6}$ in Table III for even $n$. In
a similar way, by solving (43) we can obtain $\lambda_{1}$ and $\lambda_{5}$.

The sum of all eigenvalues is

$({{p}}-{{m}})\sqrt{\frac{n-1}{2}},$ (44)

and the trace of $\mathbf{C}_{(1)}$ is zero, (10), resulting in
${{p}}={{m}}=(n-4)/2$, as stated in Table III for an even $n$.

##  VI Conclusion

An analytic proof for eigenvalues, and corresponding multiplicities is
provided for eight symmetric non-normalized DTT. The trace and the square of
transformation matrix is derived in all analyzed cases. Our further research
will include derivation of eigenvector basis for the analyzed DTT. The
proposed approach, based on the decomposition of the eigenspace into
orthogonal subspaces invariant under considered DTT, provides eigenvalues and
some eigenvectors, for the case when the eigenvalue multiplicity is 1. Since
the DTT are fundamental mathematical tools for signal processing and related
applications, we believe that the presented theory is particularly relevant to
this field, since it sheds a new light on the understanding of commonly used
transforms.

## References

  * [1] S. K. Mitra, and Y. Kuo, Digital signal processing: a computer-based approach, Vol. 2. New York: McGraw-Hill, 2006.
  * [2] L. Stanković, Digital Signal Processing with Selected Topics, CreateSpace Independent Publishing Platform, An Amazon.com Company, 2015.
  * [3] G. Strang, “The discrete cosine transform,” SIAM review vol. 41, no. 1, pp. 135-147, 1999.
  * [4] M. Püschel, and J. M. Moura, “The algebraic approach to the discrete cosine and sine transforms and their fast algorithms,” SIAM Journal on Computing, vol. 32, no. 5, pp. 1280-1316, 2003.
  * [5] M. Püschel, and J. M. Moura, “The discrete trigonometric transforms and their fast algorithms: An algebraic symmetry perspective.” Proceedings of 2002 IEEE 10th Digital Signal Processing Workshop, 2002 and the 2nd Signal Processing Education Workshop, IEEE, 2002.
  * [6] V. Britanak, P. C. Yip, and K. R. Rao, Discrete cosine and sine transforms: general properties, fast algorithms and integer approximations, Elsevier, 2010.
  * [7] N. Ahmed, T. Natarajan and K.R. Rao, “Discrete cosine transform,” IEEE transactions on Computers, vol. 100, no. 1, pp. 90-93, 1974.
  * [8] H. Ochoa-Dominguez, and K. R. Rao, Discrete Cosine Transform, CRC Press, 2019.
  * [9] S. R. Garcia, and S. Yih, “Supercharacters and the discrete Fourier, cosine, and sine transforms,” Communications in Algebra, vol. 46, no. 9, pp. 3745-3765, 2018
  * [10] C. C. Tseng, “Eigenvalues and eigenvectors of generalized DFT, generalized DHT, DCT-IV and DST-IV matrices,” IEEE Transactions on Signal Processing, vol. 50, no. 4, pp. 866-877, 2002.
  * [11] S. C. Pei and M. H. Yeh, “The Discrete Fractional Cosine and Sine Transforms,” IEEE Transactions on Signal Processing, vol. 49, no. 6, pp. 1198-1207, 2001.
  * [12] S. C. Pei and J. J. Ding, “Generalized eigenvectors and fractionalization of offset DFTs and DCTs,” IEEE Transactions on Signal Processing, vol. 52, no. 7, pp. 2032-2046, 2004.
  * [13] Ç. Candan, “On the eigenstructure of DFT matrices”, IEEE Signal Processing Magazine, vol. 28, no. 2, pp. 105-108, 2011.
  * [14] B. W. Dickinson and K. Steiglitz, “Eigenvectors and functions of the discrete Fourier transform,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 30, no. 1, pp. 25–31, 1982.
  * [15] D. Wei and Y. Li, “Novel Tridiagonal Commuting Matrices for Types I, IV, V, VIII DCT and DST Matrices,” IEEE Signal Processing Letters, vol. 21, no. 4, pp. 483-487, 2014.
  * [16] G. Cariolaro, T. Erseghe and P. Kraniauskas, “The fractional discrete cosine transform,” IEEE Transactions on Signal Processing, vol. 50, no. 4, pp. 902-911, 2002.
  * [17] I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, Elsevier, 2007.