1 Linear Algebra 1.2 Determinant Form for KummerU Function of a Matrix Argument 1.4 Novel Matrix Identities

1.3 Novel Matrix Decompositions

This is a consolidated post containing two former posts on novel matrix decompositions.

1.3.1 Offset Non-Uniform Discrete Cosine Decomposition of Toeplitz Matrices

Diagonalization of a Toeplitz matrix (or the related Henkel matrix) is well known for about 100 years due to Carathéodory. Recently, the methods and techniques were formalized and were shown to be related to non-uniform discrete Fourier transformation (DFT). In this post, we look at a straightforward extension to non-uniform discrete cosine transformation (DCT) for real-valued Toeplitz matrices.

Let $\boldsymbol{T}$ be an $N\times N$ real, symmetric, Toeplitz matrix with simple eigenvalues. The matrix admits a Vandermonde decomposition [4, 2] given by

\boldsymbol{T}=\boldsymbol{V}^{\text{H}}\boldsymbol{D}\boldsymbol{V}

where $\boldsymbol{V}$ is an $N\times N$ complex-valued Vandermonde matrix with powers of roots of unity, $\nu_{0},\dots,\nu_{N-1},$ hereafter referred to as modes, along the columns (shown below), and $\boldsymbol{D}$ is an $N\times N$ non-negative diagonal matrix.

\boldsymbol{V}=\begin{bmatrix}1&\nu_{0}&\nu_{0}^{2}&\cdots&\nu_{0}^{N-1}\\ 1&\nu_{1}&\nu_{1}^{2}&\cdots&\nu_{1}^{N-1}\\ 1&\vdots&\vdots&\ddots&\vdots\\ 1&\nu_{N-1}&\nu_{N-1}^{2}&\cdots&\nu_{N-1}^{N-1}\end{bmatrix}

Absence of a Non-Uniform Cosine Decomposition

Theorem 1 (Absence of a general NUCD).

There exists no uniform cosine decomposition

\boldsymbol{T}=\boldsymbol{C}^{\text{T}}\boldsymbol{D}\boldsymbol{C}

for the matrix $\boldsymbol{T}$ for $N>2.$

Note: $\boldsymbol{C}$ is an $N\times N$ real, cosine matrix and $\boldsymbol{D}$ an $N\times N$ positive diagonal matrix. The elements of $\boldsymbol{C}$ are given by

[\boldsymbol{C}]_{mn}=\cos(n\theta_{m}),

where $m,n=0,\dots,N-1,$ and $\theta_{m}\in(-\pi,\pi].$

Proof.

Let $\tau_{m,n}$ and $\delta_{m,n}$ denote the $(m,n)$ terms of the matrices $\boldsymbol{T}$ and $\boldsymbol{D},$ respectively. Expanding $\boldsymbol{C}^{\text{T}}\boldsymbol{D}\boldsymbol{C}$ and equating the diagonal elements we have

\tau_{n,n}=\sum_{m=0}^{N-1}\delta_{m,m}\cos^{2}(n\theta_{m}),

where $n=0,\dots,N-1.$ Therefore, the first element $\tau_{0,0}$ is

\tau_{0,0}=\sum_{m=0}^{N-1}\delta_{m,m}.

Due to the Toeplitz structure of $\boldsymbol{T}$ , we have equality of the diagonal elements, i.e., $\tau_{0,0}=\tau_{1,1}=\cdots=\tau_{N-1,N-1}.$ However, since for any $\theta\in(-\pi,\pi]$ we have $0\leq\cos^{2}(\theta)\leq 1$ with upper-bound equality only for $\theta=\{0,\pi\},$ no angles beyond $\{0,\pi\}$ can satisfy the equality of the diagonal elements. Hence, such a decomposition does not exist. ∎

Result of the above theorem motivates us to explore offset non-uniform cosine decomposition where the decomposition is scaled as $\boldsymbol{T}=\gamma^{2}\boldsymbol{C}^{\text{T}}\boldsymbol{D}\boldsymbol{C}$ for some $\gamma>1,$ wherefore equality of the diagonal elements may be met.

Offset Non-Uniform Cosine Decomposition

Lemma 2.

The modes $\nu_{1},\dots,\nu_{N-1},$ are either real or appear in complex conjugate pairs using the algorithm given in [2] with a real initial value $\nu_{0}.$

Note: The only admissible real initial values are $\nu_{0}=\pm 1.$

Proof.

Modes are the polynomial roots of $A(z)=\sum_{k=0}^{N-1}\alpha_{k}z^{k},$ where $\alpha_{k}$ is the $k$ -th element of the vector $\boldsymbol{a}$ given by solving $\boldsymbol{Ta}=\boldsymbol{v}$ [2]. Here, $\boldsymbol{v}$ is the initial value vector given by $\boldsymbol{v}=[1,\nu_{0},\nu_{0}^{2},\dots,\nu_{0}^{N-1}].$ ∎

For real initial value vectors, the coeffcients $\alpha_{k}$ of the polynomial $A(z)$ are real. Therefore, the roots of the polynomial are either real or appear in complex conjugate pairs.

Now we present the main result of this post.

Theorem 3 (O-NUCD).

For real initial values, there exists an offset non-uniform cosine decomposition $\boldsymbol{T}=2\boldsymbol{C}^{\text{T}}\boldsymbol{D}\boldsymbol{C}$ for the matrix $\boldsymbol{T}.$

Note: $\boldsymbol{C}$ is an $N\times N$ real, cosine matrix and $\boldsymbol{D}$ an $N\times N$ positive diagonal matrix. The elements of the matrix $\boldsymbol{C}$ are given by

[\boldsymbol{C}]_{m,n}=\cos\left(\mp\frac{\pi}{4}+n\theta_{m}\right),

where $m,n=0,\dots,N-1,$ and $\theta_{m}=\angle\nu_{m}.$

Proof.

Let $\boldsymbol{V}_{R}$ and $\boldsymbol{V}_{I}$ denote the real and imaginary parts of the Vandermonde matrix $\boldsymbol{V}.$ As the initial values are real, from Lemma 2, the roots are either real or have complex conjugate symmetry. Therefore, we have the following orthogonality properties:

\boldsymbol{V}_{R}^{\text{T}}\boldsymbol{V}_{I}=\boldsymbol{V}_{R}^{\text{T}}% \boldsymbol{D}\boldsymbol{V}_{I}=\boldsymbol{V}_{I}^{\text{T}}\boldsymbol{V}_{% R}=\boldsymbol{V}_{I}^{\text{T}}\boldsymbol{D}\boldsymbol{V}_{R}=\boldsymbol{0}.

Using these properties (twice), we have

\boldsymbol{T}=\boldsymbol{V}_{R}^{\text{T}}\boldsymbol{D}\boldsymbol{V}_{R}+% \boldsymbol{V}_{I}^{\text{T}}\boldsymbol{D}\boldsymbol{V}_{I}=(\boldsymbol{V}_% {R}\pm\boldsymbol{V}_{I})^{\text{T}}\boldsymbol{D}(\boldsymbol{V}_{R}\pm% \boldsymbol{V}_{I})=2\boldsymbol{C}^{\text{T}}\boldsymbol{D}\boldsymbol{C},

with the elements of the matrix $\boldsymbol{C}$ as shown above. ∎

O-NUCD in MATLAB using the Vandermonde Tools

As an example, O-NUCD ( $-\frac{\pi}{4}$ ) may be found using the Vandermonde Tools from AudioLabs [3] as follows:

⬇

>> [v,d] = find_vand('xcorr', T) ;

>> V = vandermonde_fast(v) ;

>> D = diag(d) ;

>> norm(V'*D*V - T)

ans = 2.5403e-15

>> C = cos(-pi/4 + angle(v)*(0:N-1)) ;

>> norm(2*C'*D*C - T)

ans = 2.0304e-15

Version History

1.

First published: 14th May 2019 on aravindhk-math.blogspot.com
2.

Modified: 16th Dec. 2023 – Style updates for LaTeX

1.3.2 Simultaneous Triangularization of Two Arbitrary Wide Matrices via the QR Decomposition

Simultaneous triangularization (ST) of an arbitrary number of matrices that satisfy certain algebraic properties is well known, see, e.g., [17]. However, for arbitrary wide matrices with the same number of columns, directly applying QR decomposition leads to a ”pseudo-triangular” structure, i.e., there are more non-zero columns than the number of rows. However, for just two arbitrary wide matrices, a ”true” ST scheme can be obtained exploiting their null spaces. In [12], this technique was presented and used in non-orthogonal multiple access (NOMA) downlink communication systems for interference mitigation. In the following post, an overview of the ST scheme is presented. A MATLAB example is provided.

The statement of the theorem is as follows.

Theorem 4 ([12, Theorem 2]).

Let $\boldsymbol{A}\in\mathbb{C}^{m_{1}\times n}$ and $\boldsymbol{B}\in\mathbb{C}^{m_{2}\times n},$ $m_{1},m_{2}\leq n,$ be complex-valued matrices of sizes $m_{1}\times n$ and $m_{2}\times n$ and have full row rank. Then, there exist unitary matrices $\boldsymbol{U}_{1}\in\mathbb{C}^{m_{1}\times m_{1}},\boldsymbol{U}_{2}\in% \mathbb{C}^{m_{2}\times m_{2}},$ and an invertible matrix $\boldsymbol{X}\in\mathbb{C}^{n\times n}$ such that

	$\displaystyle\boldsymbol{U}_{1}\boldsymbol{A}\boldsymbol{X}$	$\displaystyle=\begin{bmatrix}\boldsymbol{R}_{1}&\boldsymbol{0}\end{bmatrix},$		(1.1)
	$\displaystyle\boldsymbol{U}_{2}\boldsymbol{B}\boldsymbol{X}$	$\displaystyle=\begin{bmatrix}\boldsymbol{R}_{2}^{\prime}&\boldsymbol{0}&% \boldsymbol{R}_{2}^{\prime\prime}\end{bmatrix},$		(1.2)

where $\boldsymbol{R}_{1}\in\mathbb{C}^{m_{1}\times m_{1}}$ and $\boldsymbol{R}_{2}=\begin{bmatrix}\boldsymbol{R}_{2}^{\prime}&\boldsymbol{R}_{% 2}^{\prime\prime}\end{bmatrix}\in\mathbb{C}^{m_{2}\times m_{2}}$ are upper-triangular matrices with real-valued entries on their main diagonals.

As seen from the theorem, the ST scheme additionally requires the invertible matrix $\boldsymbol{X}$ apart from the unitary matrices $\boldsymbol{U}_{1}$ and $\boldsymbol{U}_{2}.$ Moreover, for $\boldsymbol{B},$ triangularization includes $n-m_{2}$ columns of zeros in the middle, which may be ignored to construct the matrix $\boldsymbol{R}_{2}.$ See [12] for generalizations of the theorem.

Below is the proof of the theorem.

Proof.

Let $\bar{\boldsymbol{A}}\in\mathbb{C}^{n\times(n-m_{1})}$ and $\bar{\boldsymbol{B}}\in\mathbb{C}^{n\times(n-m_{2})}$ be matrices that contain a basis for the null space of $\boldsymbol{A}$ and $\boldsymbol{B},$ respectively. Let $\boldsymbol{K}\in\mathbb{C}^{n\times\max(0,m_{1}+m_{2}-n)}$ denote the matrix containing a basis for the null space of $\begin{bmatrix}\bar{\boldsymbol{A}}&\bar{\boldsymbol{B}}\end{bmatrix}^{\mathrm% {H}}.$ Let, by QR decomposition,

	$\displaystyle\boldsymbol{\mathcal{U}}_{1}\boldsymbol{R}_{1}$	$\displaystyle=\boldsymbol{A}\begin{bmatrix}\boldsymbol{K}&\bar{\boldsymbol{B}}% \end{bmatrix},$		(1.3)
	$\displaystyle\boldsymbol{\mathcal{U}}_{2}\boldsymbol{R}_{2}$	$\displaystyle=\boldsymbol{B}\begin{bmatrix}\boldsymbol{K}&\bar{\boldsymbol{A}}% \end{bmatrix}.$		(1.4)

Then, (1.1) and (1.2) are satisfied by setting $\boldsymbol{X}$ to

\displaystyle\boldsymbol{X}=\begin{bmatrix}\boldsymbol{K}&\bar{\boldsymbol{B}}% &\bar{\boldsymbol{A}}\end{bmatrix},

(1.5)

and choosing $\boldsymbol{U}_{1}=\boldsymbol{\mathcal{U}}_{1}^{\mathrm{H}}$ and $\boldsymbol{U}_{2}=\boldsymbol{\mathcal{U}}_{2}^{\mathrm{H}}$ from (1.3) and (1.4) above, to obtain

	$\displaystyle\boldsymbol{U}_{1}\boldsymbol{A}\boldsymbol{X}=$	$\displaystyle\begin{bmatrix}\underbrace{\boldsymbol{\mathcal{U}}_{1}^{\mathrm{% H}}\boldsymbol{A}\begin{bmatrix}\boldsymbol{K}&\bar{\boldsymbol{B}}\end{% bmatrix}}_{\boldsymbol{R}_{1}}&\underbrace{\boldsymbol{\mathcal{U}}_{1}^{% \mathrm{H}}\boldsymbol{A}\bar{\boldsymbol{A}}}_{\boldsymbol{0}}\end{bmatrix},$		(1.6)
	$\displaystyle\boldsymbol{U}_{2}\boldsymbol{B}\boldsymbol{X}\overset{(a)}{=}$	$\displaystyle\begin{bmatrix}\underbrace{\boldsymbol{\mathcal{U}}_{2}^{\mathrm{% H}}\boldsymbol{B}\boldsymbol{K}}_{\boldsymbol{R}_{2}^{\prime}}&\underbrace{% \boldsymbol{\mathcal{U}}_{2}^{\mathrm{H}}\boldsymbol{B}\bar{\boldsymbol{B}}}_{% \boldsymbol{0}}&\underbrace{\boldsymbol{\mathcal{U}}_{2}^{\mathrm{H}}% \boldsymbol{B}\bar{\boldsymbol{A}}}_{\boldsymbol{R}_{2}^{\prime\prime}}\end{% bmatrix},$		(1.7)

where (a) holds because the QR decomposition in (1.4) is unaffected by the zero columns introduced in the middle. ∎

Next, a MATLAB-based example is provided.

⬇

% Generate compatible matrices

A = complex(randn(3,4),randn(3,4)) ;

B = complex(randn(3,4),randn(3,4)) ;

% Compute matrix X

A_bar = null(A) ;

B_bar = null(B) ;

K = null([A_bar, B_bar]') ;

X = [K, B_bar, A_bar] ;

% Triangularize the input matrices

[U_cal1, ~] = qr(A*X) ;

[U_cal2, ~] = qr(B*X) ;

U1 = U_cal1' ;

U2 = U_cal2' ;

% Demonstrate ST

U1*A*X =

-2.0667 + 0.0000i -1.4910 + 1.2510i 0.1708 - 0.4198i 0.0000 + 0.0000i

0.0000 - 0.0000i -1.0789 + 0.0000i 0.4117 - 0.4322i 0.0000 - 0.0000i

0.0000 - 0.0000i 0.0000 + 0.0000i -1.5056 - 0.0000i -0.0000 + 0.0000i

U2*B*X =

-2.0667 + 0.0000i -1.1795 + 1.0534i -0.0000 + 0.0000i -0.7368 - 0.0662i

-0.0000 - 0.0000i -2.5202 - 0.0000i 0.0000 - 0.0000i 0.9798 - 1.9193i

-0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.8765 + 1.6384i

Version History

1.

First published: 13th Aug. 2022 on aravindhk-math.blogspot.com
2.

Modified: 16th Dec. 2023 – Style updates for LaTeX
3.

Modified: 30th Dec. 2023 – Minor updates to text