1 Linear Algebra 1.4 Offset Non-Uniform Discrete Cosine Decomposition of Toeplitz Matrices 1.6 Cyclic Shifts Property of Trace with Hadamard Products

1.5 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