Effective Methods of QR-Decompositions of Square Complex Matrices by Fast Discrete Signal-Induced Heap Transforms

Artyom M. Grigoryan

Department of Electrical and Computer Engineering, The University of Texas at San Antonio, San Antonio, USA.

DOI: 10.4236/alamt.2022.124005                

Abstract

The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 2006) is used. This transform is fast, has a unique algorithm for any length of the input vector/signal and can be used with different complex basic 2 × 2 transforms. The DsiHT is zeroing all components of the input signal while moving or heaping the energy of the signal to one component, for instance the first one. We describe three different types of QR-decompositions that use the basic transforms with the T, G, and M-type complex matrices we introduce, as well as without matrices but using analytical formulas. We also present the mixed QR-decomposition, when different type DsiHTs are used in different stages of the algorithm. The number of such decompositions is greater than 3^(N-1), for an N × N complex matrix. Examples of the QR-decomposition are described in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the known method of Householder transforms. The precision of the QR-decompositions of N × N matrices, when N are 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400 is also compared. The MATLAB-based scripts of the codes for QR-decompositions by the described DsiHTs are given.

Keywords

QR Decomposition, Signal-Induced Heap Transform, Householder Transform, Givens Rotations

1. Introduction

The QR-decomposition, or factorization of a non-singular matrix $A=QR$ into a unitary matrix Q and an upper triangular matrix R, as well as the factorization $A=QL$ with a low triangular matrix L are powerful tools for solving linear systems of equations $y=Ax$ in many applications in computing and data analysis [1] - [7] . Here, the matrix A is a real or complex non-singular matrix. The matrix Q is unitary, and therefore its inverse is the transpose conjugate $Q^{\ast }$ matrix. The calculation of inverse of the triangular matrix is not a difficult task. Therefore, the solution of the system of equation can be calculated by $x=A^{-1}y=R^{-1}{Q}^{\ast }y$ for the QR-decomposition, and $x=A^{-1}y=L^{-1}{Q}^{\ast }y$ for the QL-decomposition. Many known methods of QR-decomposition of real matrices were modified for the complex case. They include the Gramm-Schmidt process [8] , the method of Householder transformations (or Householder reflections) [9] , and the Givens rotations [10] [11] [12] .

In this work, we focus on the QR-decomposition and describe three types of decompositions, by using the concept of the discrete signal-induced heap transform (DsiHT) [13] [14] [15] . In the case of real matrices, the detail description of the DsiHT method of QR-decomposition is given in [16] . For complex matrices, there are different types of 2 × 2 basic complex unitary transforms can that transfer energy of the 2-point signal to the first components, while zeroing the second one. The path of the DsiHT, i.e., the order of sequential processing (or rotating in some cases) of data of the signal is an important characteristic of the transform. The DsiHTs with different paths result in different QR-decomposition of the same matrix, as shown in [17] on examples with the so-called weak and strong-DsiHTs. The interesting property of the QR-decomposition by the DsiHT is in the presence of analytical equations that allow calculating the transforms and their matrices without using the basic matrices of rotations. The case with complex matrices is much richer than real matrices, since there are many different basic transforms, not only “Givens rotations,” that can be considered in the DsiHT. Examples of such transforms and their application in QR-decom- position of complex matrices are described and compared with the complex Householder transform-based QR-decomposition.

The rest of this paper is organized in the following way. In Section 2, the concept of the DsiHT is described with examples of two-wheel carriages that illustrate the performance of the transform. The basic complex matrices of the 2 × 2 transforms composing the N-point DsiHT are described in Section 3. These matrices are classified by the basic transforms use them and are called the T, G, and M-type complex matrices. The concept of the DsiHT which can be calculated without matrices but by analytical formulas is also described. The QR-decom- positions with three types of DsiHTs are presented with examples in Section 4. It is shown that the M-type DsiHT based QR decomposition is close to the result of the Householder transform method, and other two types of QR-decomposi- tion differ much. The scripts for MATLAB-based codes for computing the DsiHT and described QR-decompositions are given in Section 5. In Section 6, the concept of the mixed QR-decomposition is presented, when different type DsiHTs are used in different stages of decomposition. The number of such decompositions is greater than $3^{\left(N-1\right)}$ for an N × N complex matrices, which is a very large number for large N. The questions related to the selection of the QR-decompo- sition from such large number of cases are not discussed here in detail, since it beyond the score of this work.

2. Basic 2 × 2 Matrices in Complex Algebra

In this section, we describe briefly the concept of the discrete signal-induced heap transform (DsiHT) [13] [15] . The transform is unitary and is defined by a non-zero vector, or signal $x=\left(x_0,x_1,x_2,\cdots ,x_{N-1}\right)$ , without any constrain on the length N and signal itself; it may be real and complex. This signal is called the generator of the DsiHT; the signal generates the unitary transform which is applying on other signals $z=\left(z_0,z_1,z_2,\cdots ,z_{N-1}\right)$ . We consider the case when the N-point DsiHT is calculating by (N − 1) basic transformations T, each of which is applying only on two components of the renewal vector z in a certain order, or a path.

In the simple form, the DsiHT is calculated by applying a set of basic transformations T. The 2 × 2 matrix of such a transformation is defined by a chosen vector $\left(x,y\right)$ from the condition

$T\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}{x}^{\prime }\\ 0\end{array}\right]\text{and}{\left|x^{\prime }\right|}^2=\sqrt{x^2+y^2}.$ (1)

In the case when x and y are real, T can be considered as the Givens rotation with the matrix

$T=T_{\phi }=\left[\begin{array}{rr}\hfill \cos \phi & \hfill -\sin \phi \\ \hfill \sin \phi & \hfill \cos \phi \end{array}\right],\phi =-\arctan \left(\frac{y}{x}\right).$

If $x=0$ , the angle of rotation $\phi =-\pi /2$ , or $\pi /2$ .

The concept of the N-point DsiHT of the signal z is illustrated in the diagram of Figure 1. This is the so-called weak carriage with two wheels, one “rotates” the generator x and another wheel “rotates” the signal z. When the carriage moves, the generator components work together with the first element x₀ and update/renew its value at each step. At the same time, the transformation T, which is determined during the rotation of the first wheel, is applying to the two

Figure 1. The two-wheel carriage of the DsiHT.

components of the input signal z. In this wheel, the components of z are processing together with the first element z₀ and update its value.

The N-point DsiHT with such a carriage is called a weak DsiHT, since the components $x_n$ and $z_n$ of the generator and signal are processed in the natural order of the index n, i.e., $x_0$ with $x_1$ , then $x_2,x_3,\cdots ,x_{N-1}$ , and the same for the signal z. This is the natural path of the DsiHT and the path can be chosen differently [16] [18] . For instance, the concept of the strong DsiHT is defined by the path in order $x_{N-1}$ with $x_{N-2}$ , then $x_{N-3},\cdots ,x_1,x_0$ , and the same for the signal z. The carriage of the strong DsiHT is illustrated in Figure 2.

We consider the DsiHT with the natural path.

Algorithm of the DsiHT with the generator $x=\left(x_0,x_1,x_2,\cdots ,x_{N-1}\right)$ .

The input signal is $z=\left(z_0,z_1,z_2,\cdots ,z_{N-1}\right)$ .

1) Stage $k=1$ .

· Calculate the matrix of the transform $T_1$ that is generated by the vector ${\left(x_0,x_1\right)}^{\prime }$ .

· Calculate the transform $T_1:{\left(z_0,z_1\right)}^{\prime }\to {\left(z_0^{\left(1\right)},{z^{\prime }}_1\right)}^{\prime }$ .

· Calculate the new value $x_0^{\left(1\right)}$ of $x_0$ in the transform $T_1:{\left(x_0,x_1\right)}^{\prime }\to {\left(x_0^{\left(1\right)},0\right)}^{\prime }$ .

2) Stage $k=2$ .

· Calculate the matrix of the transform $T_k$ that is generated by the vector ${\left(x_0^{\left(k-1\right)},x_k\right)}^{\prime }$ .

· Calculate the transform $T_k:{\left(z_0^{\left(k-1\right)},z_k\right)}^{\prime }\to {\left(z_0^{\left(k\right)},{z^{\prime }}_k\right)}^{\prime }$ .

· Calculate the new value $x_0^{\left(k\right)}$ in the transform $T_2:{\left(x_0^{\left(k-1\right)},x_k\right)}^{\prime }\to {\left(x_0^{\left(k\right)},0\right)}^{\prime }$ .

3) Stage $k=3,4,\cdots ,N-1$ .

· Continue calculations as in Step 2, to get the rest values of the output ${z^{\prime }}_3,{z^{\prime }}_4,\cdots ,{z^{\prime }}_{N-1}$ , and $z_0^{\left(N\right)}$ .

The output signal is $z^{\prime }=\left(z_0^{\left(N\right)},{z^{\prime }}_1,{z^{\prime }}_2,{z^{\prime }}_3,\cdots ,{z^{\prime }}_{N-1}\right)$ .

To simplicity the notations in the two-wheel carriage in Figure 1, ${x^{\prime }}_0$ denotes $x_0^{\left(k\right)}$ and ${z^{\prime }}_0$ denotes $z_0^{\left(k\right)}$ on the kth stage of rotations. Thus, during the composition of the N-point DsiHT, H, a set of parameters, or angles ${\phi }_1,{\phi }_2,\cdots ,{\phi }_{N-1}$ , is calculated, which is called the angular representation of the generator x [15] .

Figure 2. The two-wheel carriage of the strong DsiHT.

The transformation H is separable and calculated as

$H=T_{{\phi }_{N-1}}\cdots T_{{\phi }_3}{T}_{{\phi }_2}{T}_{{\phi }_1}.$ (2)

When $z=x$ , the transform of the vector x is collected to one heap; it is transferred to the first component, $T\left(x\right)=\left(x_0^{\left(N-1\right)},0,0,\cdots ,0\right)$ , where $x_0^{\left(N-1\right)}=\Vert x\Vert =\sqrt{x_0^2+x_1^2+\cdots +x_{N-1}^2}$ .

Example 1: For the $N=6$ case, we consider the generator $x=\left(1,1,2,4,3,1\right)$ with the norm $\Vert x\Vert =\sqrt{32}=5.6569$ . The matrix and the set of five angles (in radians) of the 6-point x-DsiHT are

$H_1=\left(\begin{array}{cccccc}0.1768& 0.1768& 0.3536& 0.7071& 0.5303& 0.1768\\ -0.7071& 0.7071& 0& 0& 0& 0\\ -0.5774& -0.5774& 0.5774& 0& 0& 0\\ -0.3482& -0.3482& -0.6963& 0.5222& 0& 0\\ -0.1149& -0.1149& -0.2298& -0.4595& 0.8424& 0\\ -0.0318& -0.0318& -0.0635& -0.1270& -0.0953& 0.9843\end{array}\right),$

$\left\{{\phi }_1,{\phi }_2,{\phi }_3,{\phi }_4,{\phi }_5\right\}=\left\{-0.7854,-0.9553,-1.0213,-0.5690,-0.1777\right\}.$

The matrix $H_1$ of the transform can be written as $H_1=D_1{A}_1$ , where the diagonal matrix

$D_1=\text{diag}\left\{0.1768,-0.7071,-0.5774,-0.3482,-0.1149,-0.0318\right\}$

and the matrix $A_1$ is

$A_1=\left(\begin{array}{cccccc}1& 1& 2& 4& 3& 1\\ 1& -1& 0& 0& 0& 0\\ 1& 1& -1& 0& 0& 0\\ 1& 1& 2& -1.5& 0& 0\\ 1& 1& 2& 4& -22/3& 0\\ 1& 1& 2& 4& 3& -31\end{array}\right).$

The determinant of the matrix $\det H_1=1$ . The first row of the matrix $A_1$ is the generator x and the last row is the same generator only with the splash at the end. This value is calculated by $31=1+1+2^2+4^2+3^2$ ; it is the energy of the generator without the last component, i.e., ${\Vert x\Vert }^2-1$ .

For the 6-point DsiHT with the path of the strong carriage, we have the following data. The angular representation is

$\left\{{\phi }_1,{\phi }_1,\cdots ,{\phi }_6\right\}=\left\{-1.3931,-1.3902,-1.1970,-0.6690,-0.3218\right\}$ ,

and the matrix $H_2$ of this DsiHT with $\det H_2=1$ is

$H_2=\left(\begin{array}{cccccc}0.1768& 0.1768& 0.3536& 0.7071& 0.5303& 0.1768\\ -0.9843& 0.0318& 0.0635& 0.1270& 0.0953& 0.0318\\ 0& -0.9837& 0.0656& 0.1312& 0.0984& 0.0328\\ 0& 0& -0.9309& 0.2864& 0.2148& 0.0716\\ 0& 0& 0& -0.6202& 0.7442& 0.2481\\ 0& 0& 0& 0& -0.3162& 0.9487\end{array}\right).$

This matrix can be presented as

$H_2=D_2{A}_2,A_2=\left(\begin{array}{cccccc}1& 1& 2& 4& 3& 1\\ -31& 1& 2& 4& 3& 1\\ 0& -30& 2& 4& 3& 1\\ 0& 0& -13& 4& 3& 1\\ 0& 0& 0& -2.5& 3& 1\\ 0& 0& 0& 0& -1/3& 1\end{array}\right).$

Here, the diagonal matrix $D_2=\text{diag}\left\{0.1768,0.0318,0.0328,0.0716,0.2481,0.9487\right\}$ . Thus, we have two different matrices $H_1$ and $H_2$ such that

$H_1{x}^{\prime }=H_2{x}^{\prime }={\left(\Vert x\Vert ,0,0,0,0,0\right)}^{\prime }={\left(5.6569,0,0,0,0,0\right)}^{\prime }.$

If we take a vector z, for instance equal $z=\left(4,-2,3,-1,7,2\right)$ with the norm $\Vert z\Vert =9.1104$ , we obtain the following transforms:

$z_1=H_1{z}^{\prime }={\left(4.7730,-4.2426,0.5774,-3.3075,5.4375,1.1748\right)}^{\prime },$

$z_2=H_2{z}^{\prime }={\left(4.7730,-3.2068,2.7873,-1.4322,6.3258,-0.3162\right)}^{\prime },$

and $\Vert z_1\Vert =\Vert z_2\Vert =9.1104=\Vert z\Vert$ .

Below are the script of the MATLAB-based code to calculate the matrices of these two DsiHTs.

Calculation of the DsiHT by Analytical Equations

It is important to note that the N-point DsiHT can be obtained without calculation of the angles ${\phi }_k$ and trigonometric functions $\cos {\phi }_k$ and $\sin {\phi }_k$ , but by using the analytical formulas [16] . For that, we consider the following notations, which represent respectively the partial cross-correlation of z with the vector generator x:

$E_k\left(z,x\right)=z_0{x}_0+z_1{x}_1+\cdots +z_k{x}_k$ , (3)

and the partial and full energies of the signal generator

$E_k^2\left(x\right)=E_k\left(x,x\right)=x_0^2+x_1^2+\cdots +x_k^2,k=0,1,\cdots ,\left(N-1\right).$ (4)

The components of the DsiHT on the k-th iteration can be expressed by the correlation data as follows:

$z_k^{\left(1\right)}=\frac{E_k\left(x,x\right)z_k-E_k\left(z,x\right)x_k}{E_{k-1}\left(x\right)E_k\left(x\right)},k=1,2,\cdots ,\left(N-1\right).$ (5)

On the final stage, the value of the first component is defined by

$z_0^{\left(N-1\right)}=E_{N-1}\left(z,x\right)/E_{N-1}\left(x\right),$ (6)

which is the correlation coefficient of the input signal z with the normalized generator x. For a given generator, all values of $E_k\left(x,x\right)$ and $E_{k-1}\left(x\right)E_k\left(x\right)$ can be calculated in advance. In the case when $z=x$ ,

$x_0^{\left(N-1\right)}=\frac{E_{N-1}\left(x,x\right)}{E_{N-1}^2\left(x\right)}=\Vert x\Vert$

and $x_k^{\left(1\right)}=0$ , for all $k=1,2,\cdots ,\left(N-1\right)$ .

The coefficients $h_{n,m}$ of the matrix of the N-point DsiHT can be obtained from Equations (3)-(6). The m-th column of the DsiHT matrix H can be calculated, by applying the unit vector $e_m={\left(0,0,\cdots ,1,\cdots ,0\right)}^{\prime }$ with 1 on the m-th position, where $m\in \left\{0,1,\cdots ,N-1\right\}$ . Therefore, the coefficients of the transform can be calculated by

$h_{0,m}=\frac{E_{N-1}\left(e_m,x\right)}{E_{N-1}\left(x\right)},m=0:\left(N-1\right),$ (7)

$h_{n,m}=\frac{E_n^2\left(x\right){\left(e_m\right)}_n-E_n\left(e_m,x\right)x_n}{E_{n-1}\left(x\right)E_n\left(x\right)},$ (8)

where $n=1:\left(N-1\right)$ .

3. Complex Basic Matrices

The N-point DsiHT is calculated, by applying (N − 1) basic transformations T on two different components of the renewal vector in a certain order, or the path. In this section, we consider the concept of the complex DsiHT. The basic transformation of the DsiHT, which is defined by a complex vector ${\left(x_0,x_1\right)}^{\prime }$ , and then, is applied to a complex input ${\left(z_0,z_1\right)}^{\prime }$ is calculated as follows:

$T:\left[\begin{array}{c}{z}_0\\ z_1\end{array}\right]\to \left[\begin{array}{c}{z^{\prime }}_0\\ {z^{\prime }}_1\end{array}\right]=\frac{\text{sign}\left(\text{Real}\left(x_0\right)\right)}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{rr}\hfill {\bar{x}}_0& \hfill {\bar{x}}_1\\ \hfill -x_1& \hfill x_0\end{array}\right]\left[\begin{array}{c}{z}_0\\ z_1\end{array}\right].$ (9)

The complex matrix of this transformation is

$T=\frac{\text{sign}\left(\text{Real}\left(x_0\right)\right)}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{rr}\hfill {\bar{x}}_0& \hfill {\bar{x}}_1\\ \hfill -x_1& \hfill x_0\end{array}\right]$

and the determinant is 1. It is not difficult to verify that the matrix T is unitary, i.e., the multiplication of T with its conjugate transpositon $T\left(\overline{T^{\text{T}}}\right)=I$ , where I is the 2 × 2 identity matrix.

When the input equals to the generator, i.e., ${\left(z_0,z_1\right)}^{\prime }={\left(x_0,x_1\right)}^{\prime }$ , we obtain the real transform

$T:\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]\to \text{sign}\left(\text{Real}\left(x_0\right)\right)\left[\begin{array}{c}\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}\\ 0\end{array}\right].$ (10)

3.1. DsiHT with Analytical Equations

The complex DsiHT can also be calculated by using analytical Equations (5) and (6), similar to the case with real vectors. For complex vectors, the partial cross- correlation of z with the vector—generator x in the first k components is calculated by

$E_k\left(z,x\right)=z_0{\bar{x}}_0+z_1{\bar{x}}_1+\cdots +z_k{\bar{x}}_k$ , (11)

and the energies in the first k components of the signal-generator by

$E_k^2\left(x\right)=E_k\left(x,x\right)={\left|x_0\right|}^2+{\left|x_1\right|}^2+\cdots +{\left|x_k\right|}^2,k=0,1,\cdots ,\left(N-1\right).$ (12)

The 2 × 2 matrix calculated by analytical Equations (7) and (8) for the $N=2$ case will be denoted by M. This matrix is different from matrix T and equals

$M=\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{rr}\hfill {\bar{x}}_0& \hfill {\bar{x}}_1\\ \hfill -x_1\frac{{\bar{x}}_0}{\left|x_0\right|}& \hfill \left|x_0\right|\end{array}\right].$ (13)

One coefficient of the matrix is a real number, and all coefficients are complex in the matrix T. The matrix M is unitary and the determinant of the matrix is the complex number

$\det M=\frac{1}{{\left|x_0\right|}^2+{\left|x_1\right|}^2}\left[{\bar{x}}_0\left|x_0\right|+{\bar{x}}_1{x}_1\frac{{\bar{x}}_0}{\left|x_0\right|}\right]=\frac{{\bar{x}}_0}{\left|x_0\right|}$ (14)

and $\left|\det M\right|=1$ . The matrix product $M{\left(x_0,x_1\right)}^{\prime }$ equals

$\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{rr}\hfill {\bar{x}}_0& \hfill {\bar{x}}_1\\ \hfill -x_1\frac{{\bar{x}}_0}{\left|x_0\right|}& \hfill \left|x_0\right|\end{array}\right]\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{c}{\left|x_0\right|}^2+{\left|x_1\right|}^2\\ 0\end{array}\right]=\left[\begin{array}{c}\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}\\ 0\end{array}\right].$

3.2. DsiHT with Complex Givens Rotations

We consider the known complex Givens rotation [4] which is defined by the matrix

$G=\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{cc}\left|x_0\right|& \text{sign}\left(x_0\right){\bar{x}}_1\\ -\overline{\text{sign}}\left(x_0\right)x_1& \left|x_0\right|\end{array}\right]=\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{cc}\left|x_0\right|& \frac{x_0}{\left|x_0\right|}{\bar{x}}_1\\ -x_1\frac{{\bar{x}}_0}{\left|x_0\right|}& \left|x_0\right|\end{array}\right].$ (15)

Here, the complex sign function is defined by $\text{sign}\left(x_0\right)=x_0/\left|x_0\right|$ . The determinant of this matrix is 1. For the $x_0=0$ case, the above matrix is defined as

$G=\frac{1}{\left|x_1\right|}\left[\begin{array}{cc}0& {\bar{x}}_1\\ -x_1& 0\end{array}\right],$

i.e., it is considered that $\text{sign}\left(0\right)=1$ . The matrix G is half-complex, meaning that in each row and column there is a real number $\left|x_0\right|$ . It should be noted that all coefficients of the basic matrix T in Equation (9) are complex numbers. When applying the matrix G on the vector-generator ${\left(x_0,x_1\right)}^{\prime }$ we obtain

$G\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{c}\left|x_0\right|x_0+\frac{x_0}{\left|x_0\right|}{\left|x_1\right|}^2\\ 0\end{array}\right]=\frac{x_0}{\left|x_0\right|}\left[\begin{array}{c}\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}\\ 0\end{array}\right],$

or

$G\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=\text{sign}\left(x_0\right)\left[\begin{array}{c}\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}\\ 0\end{array}\right],$ (16)

where $\text{sign}\left(x_0\right)$ is a complex number with norm 1. The matrix G is unitary, i.e., $G\left(\overline{G^{\text{T}}}\right)=I$ .

It should be noted that one can express the matrix G by T and by M, as

$G=\text{sign}\left(\text{Real}\left(x_0\right)\right)\left[\begin{array}{rr}\hfill \frac{x_0}{\left|x_0\right|}& \hfill 0\\ \hfill 0& \hfill \frac{{\bar{x}}_0}{\left|x_0\right|}\end{array}\right]T,G=\left[\begin{array}{rr}\hfill \frac{x_0}{\left|x_0\right|}& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right]M.$ (17)

Example 2: Let us consider two complex numbers $x_0=1+3i$ and $x_1=-2+5i$ . For these numbers, ${\left|x_0\right|}^2=1+3^2=10$ and ${\left|x_1\right|}^2=2^2+5^2=29$ . We obtain the following matrices:

$T=\frac{\text{sign}\left(\text{Real}\left(x_0\right)\right)}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{rr}\hfill {\bar{x}}_0& \hfill {\bar{x}}_1\\ \hfill -x_1& \hfill x_0\end{array}\right]=\frac{1}{\sqrt{39}}\left[\begin{array}{rr}\hfill 1-3i& \hfill -2-5i\\ \hfill 2-5i,& \hfill 1+3i\end{array}\right],$

$M=\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{rr}\hfill {\bar{x}}_0& \hfill {\bar{x}}_1\\ \hfill -x_1\frac{{\bar{x}}_0}{\left|x_0\right|}& \hfill \left|x_0\right|\end{array}\right]=\frac{1}{\sqrt{39}}\left[\begin{array}{rr}\hfill 1-3i& \hfill -2-5i\\ \hfill \frac{-13-11i}{\sqrt{10}}& \hfill \sqrt{10}\end{array}\right],$

and

$G=\frac{1}{\sqrt{{\left|x_0\right|}^2+{\left|x_1\right|}^2}}\left[\begin{array}{cc}\left|x_0\right|& \frac{x_0}{\left|x_0\right|}{\bar{x}}_1\\ -x_1\frac{{\bar{x}}_0}{\left|x_0\right|}& \left|x_0\right|\end{array}\right]=\frac{1}{\sqrt{39}}\left[\begin{array}{cc}\sqrt{10}& \frac{13-11i}{\sqrt{10}}\\ \frac{-13-11i}{\sqrt{10}}& \sqrt{10}\end{array}\right].$

The determinants of these matrices, $\det T=\det G=1$ , $\det M=0.3162-0.9487i$ , and $\left|\det M\right|=1$ . Up to the coefficient $1/\sqrt{39}$ , the ma- trix T is integer-valued for integer complex generator, and matrices G and M are more complicated; they have additional coefficients with $\sqrt{10}=3.1623$ . When applying these matrices on the vector ${\left(x_0,x_1\right)}^{\prime }={\left(1+3i,-2+5i\right)}^{\prime }$ , we obtain the following vectors:

$T\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=M\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=\left[\begin{array}{c}6.2450\\ 0\end{array}\right],G\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=\left[\begin{array}{c}1.9748+5.9245i\\ 0\end{array}\right],$

and $\left|1.9748+5.9245i\right|=6.2450$ . Thus, the results of the transforms T and M are different from G in the first component which is complex. Now, we consider the transforms of the vector $z={\left(z_0,z_1\right)}^{\prime }={\left(-7+2i,3-5i\right)}^{\prime }$ ,

$T\left[\begin{array}{c}{z}_0\\ z_1\end{array}\right]=\left[\begin{array}{r}\hfill -5.1241+2.8823i\\ \hfill 2.2418+6.8855i\end{array}\right],M\left[\begin{array}{c}{z}_0\\ z_1\end{array}\right]=\left[\begin{array}{r}\hfill -5.1241+2.8823i\\ \hfill 7.2411+0.0506i\end{array}\right],$

$G\left[\begin{array}{c}{z}_0\\ z_1\end{array}\right]=\left[\begin{array}{r}\hfill -4.3548-3.9497i\\ \hfill 7.2411+0.0506i\end{array}\right].$

The outputs of T, M, and G are different. The matrix M has commom with matrices T and G. The second components of the transform G and M are the same, and the first components of the transform T and M are the same. For all these transforms, the energy of the input vector is preserved,

${5.1241}^2+{2.8823}^2={4.3548}^2+{3.9497}^2=34.5641$ ,

${7.2411}^2+{0.0506}^2=52.4359$ ,

${2.24181}^2+{6.88551}^2=52.4359$ ,

$34.5641+52.4359=87=\left(7^2+2^2\right)+\left(3^2+5^2\right)={\left|z\right|}^2$ .

To describe the difference between the DsiHT generated by basic 2 × 2 transforms of different types, we consider the matrices of these DsiHTs for the $N=4$ case.

Example 3: The complex vector-generator is

$x=\left(x_0,x_1,x_2,x_3\right)=\left(7+4i,3+7i,-6+2i,1+2i\right).$

We have the following 4 × 4 matrices of the DsiHT calculated with basic transforms T, M, and G:

$\begin{array}{l}{T}_{4\times 4}=\left[\begin{array}{rrrr}\hfill 0.5401& \hfill 0.2315& \hfill -0.4629& \hfill 0.0772\\ \hfill -0.2705& \hfill 0.6312& \hfill 0& \hfill 0\\ \hfill 0.2401& \hfill 0.0282& \hfill 0.8687& \hfill 0\\ \hfill -0.0906& \hfill -0.1027& \hfill 0.0121& \hfill 0.9850\end{array}\right]\\ +i\left[\begin{array}{cccc}-0.3086& -0.5401& -0.1543& -0.1543\\ -0.6312& 0.3607& 0& 0\\ -0.2684& -0.3390& 0& 0\\ -0.0604& 0.0060& 0.0846& 0\end{array}\right],\end{array}$

$\begin{array}{l}{M}_{4\times 4}=\left[\begin{array}{rrrr}\hfill 0.5401& \hfill 0.2315& \hfill -0.4629& \hfill 0.0772\\ \hfill -0.5480& \hfill 0.7269& \hfill 0& \hfill 0\\ \hfill 0.2401& \hfill 0.0282& \hfill 0.8687& \hfill 0\\ \hfill -0.0906& \hfill -0.1027& \hfill 0.0121& \hfill 0.9850\end{array}\right]\\ +i\left[\begin{array}{cccc}-0.3086& -0.5401& -0.1543& -0.1543\\ -0.4138& 0& 0& 0\\ -0.2684& -0.3390& 0& 0\\ -0.0604& 0.0060& 0.0846& 0\end{array}\right],\end{array}$

$\begin{array}{l}{G}_{4\times 4}=\left[\begin{array}{rrrr}\hfill 0.6220& \hfill 0.4687& \hfill -0.3254& \hfill 0.1435\\ \hfill -0.5480& \hfill 0.7269& \hfill 0& \hfill 0\\ \hfill 0.2401& \hfill 0.0282& \hfill 0.8687& \hfill 0\\ \hfill -0.0906& \hfill -0.1027& \hfill 0.0121& \hfill 0.9850\end{array}\right]\\ +i\left[\begin{array}{cccc}0& -0.3541& -0.3636& -0.0957\\ -0.4138& 0& 0& 0\\ -0.2684& -0.3390& 0& 0\\ -0.0604& 0.0060& 0.0846& 0\end{array}\right].\end{array}$

The determinants of these matrices equal $\det T=\det G=1$ , $\det M=0.8622-0.4961i$ , and $\left|\det M\right|=1$ . The matrices $T_{4\times 4}$ and $M_{4\times 4}$ are different only in coefficients of the 2^nd rows. The difference of the matrices $T_{4\times 4}$ and $G_{4\times 4}$ is in the first two rows. In the matrices $T_{4\times 4}$ and $M_{4\times 4}$ , the first rows are proportional to the vector generator. Indeed, for the matrix $T_{4\times 4}$ we have

${\left(T_{4\times 4}\right)}_{0,0:3}={\left(M_{4\times 4}\right)}_{0,0:3}=\overline{\left(7+4i,3+7i,-6+2i,1+2i\right)}\frac{0.5401}{7}=\left(0.5401/7\right)\bar{x}.$

The vector-generator x is not in the first row of matrix G. The first coefficient of this matrix is the real number 0.6220, not complex as in the vector-generator.

For the input vector $z=\left(2-3i,1-4i,-7+i,3+5i\right)$ , the transforms equal

$T_{4\times 4}z=\left(2.6232-3.1632i,-0.3607-2.6148i,-7.7334-0.8404i,2.3447+4.9129i\right),$

$M_{4\times 4}z=\left(2.6232-3.1632,-1.6105-2.0914i,-7.7334-0.8404i,2.3447+4.9129i\right),$

$G_{4\times 4}z=\left(3.8469-1.4450i,-1.6105-2.0914i,-7.7334-0.8404i,2.3447+4.9129i\right)\text{.}$

It is not difficult to verify that in the general $N\ge 4$ case, the difference between the matrices $T_{N\times N}$ and $G_{N\times N}$ is only in the coefficeints of the first two rows. Thus, the DsiHT of signals differ only in the first components of the transform, if instead of the basic matrices T the matrices G are used.

As illustrative example, we consider the complex signal z of length 500 with real and imaginary parts shown in Figure 3 in parts (a) and (b), respectively.

The signal-generator x is calculated by

$x\left(n\right)=4+i{\left(-1\right)}^2/8,n=0:499.$

The complex signal z after processing by the DsiHT with generator x is shown in Figure 4. The basic transforms of this DsiHT are with the matrices of type T.

The results of the DsiHT of the signal z, when using matrices of types M and G are almost the same as for the T-type DsiHT. As mentioned above, the difference of these transforms is in the first two components;

$T\text{-basedDsiHT}=\left\{1962.3+389.2i,-5.3-3.9i,-9.8-9.6i,\cdots \right\},$

$M\text{-basedDsiHT}=\left\{1962.3+389.2i,-5.1-4.1i,-9.8-9.6i,\cdots \right\},$

$G\text{-basedDsiHT}=\left\{1973.5+327.8i,-5.1-4.1i,-9.8-9.6i,\cdots \right\}.$

Thus, we have three types of matrices T, M, and G for basic transforms that

(a) (b)

Figure 3. The complex signal z of length 500; (a) real and (b) imaginary parts.

(a) (b)

Figure 4. The 500-point T-type DsiHT of the signal z; (a) real and (b) imaginary parts.

can be used in the QR decomposition by the DsiHT. These matrices are different, but these transforms move the energy of vector $x=\left(x_0,x_1\right)$ to the first component and zeroing the second one.

4. QR Decompositions with the DsiHT

In this section, we analyze the application of the DsiHTs that are based on basic transformations T, M and G in QR decomposition of a square complex matrix. The QR-decomposition is described in detail on the example with a 4 × 4 matrix. Let X be the following 4 × 4 complex square matrix with $\det \left(X\right)\ne 0$ :

$X=\left[\begin{array}{llll}{a}_0\hfill & b_0\hfill & c_0\hfill & d_0\hfill \\ a_1\hfill & b_1\hfill & c_1\hfill & d_1\hfill \\ a_2\hfill & b_2\hfill & c_2\hfill & d_2\hfill \\ a_3\hfill & b_3\hfill & c_3\hfill & d_3\hfill \end{array}\right]$ .

First, we take the first column of the matrix as the vector $a={\left(a_0,a_1,a_2,a_3\right)}^{\prime }$ . This vecor will be the generator for the DsiHT, which we consider of the type M. We denote the matrix of DsiHT by $T_a$ . The application of the DsiHT on the same vector is a vector $\bar{a}=T_a\left(a\right)={\left(\Vert a\Vert ,0,0,0\right)}^{\prime }$ , where $\Vert a\Vert$ is the energy of the vector, $\Vert a\Vert =\sqrt{{\left|a_0\right|}^2+{\left|a_1\right|}^2+{\left|a_2\right|}^2+{\left|a_3\right|}^2}$ . Therefore, when multiplying the matrices $T_a$ and X, we obtain the matrix $X_1$ of the following form:

$X_1=T_{a}X=\left[\begin{array}{cccc}\Vert a\Vert & {\hat{b}}_0& {\hat{c}}_0& {\hat{d}}_0\\ 0& {\hat{b}}_1& {\hat{c}}_1& {\hat{d}}_1\\ 0& {\hat{b}}_2& {\hat{c}}_2& {\hat{d}}_2\\ 0& {\hat{b}}_3& {\hat{c}}_3& {\hat{d}}_3\end{array}\right],Y_1=\left[\begin{array}{lll}{\hat{b}}_1\hfill & {\hat{c}}_1\hfill & {\hat{d}}_1\hfill \\ {\hat{b}}_2\hfill & {\hat{c}}_2\hfill & {\hat{d}}_2\hfill \\ {\hat{b}}_3\hfill & {\hat{c}}_3\hfill & {\hat{d}}_3\hfill \end{array}\right].$

In the second step, this 3 × 3 complex submatrix $Y_1$ is processed similarly.

The first vector-column $b={\left({\hat{b}}_1,{\hat{b}}_2,{\hat{b}}_3\right)}^{\prime }$ is used as a generator for the 3-point

DsiHT. We denote by $T_b$ the matrix of this DsiHT. As a result, we obtain the following matrix:

$X_2=\left[\begin{array}{cc}1& 0\\ 0& T_b\end{array}\right]X_1=\left(1\oplus T_b\right)X_1=\left(1\oplus T_b\right)T_{a}X=\left[\begin{array}{cccc}\Vert a\Vert & {\hat{b}}_0& {\hat{c}}_0& {\hat{d}}_0\\ 0& \Vert b\Vert & {\tilde{c}}_1& {\tilde{d}}_1\\ 0& 0& {\tilde{c}}_2& {\tilde{d}}_2\\ 0& 0& {\tilde{c}}_3& {\tilde{d}}_3\end{array}\right]$

Here, $\Vert b\Vert =\sqrt{{\left|{\hat{b}}_1\right|}^2+{\left|{\hat{b}}_2\right|}^2+{\left|{\hat{b}}_3\right|}^2}$ . In the last stage of calculation, the basic trans-

form with the vector-generator $c={\left({\tilde{c}}_2,{\tilde{c}}_3\right)}^{\prime }$ is applied on two vectors ${\left({\tilde{c}}_2,{\tilde{c}}_3\right)}^{\prime }$ and ${\left({\tilde{d}}_2,{\tilde{d}}_3\right)}^{\prime }$ . Denoting by $T_c$ the matrix of this transform, we obtain the final triangularization,

$R=\left(1\oplus 1\oplus T_c\right)X_2=\left(1\oplus 1\oplus T_c\right)\left(1\oplus T_b\right)T_{a}X=\left[\begin{array}{cccc}\Vert a\Vert & {\hat{b}}_0& {\hat{c}}_0& {\hat{d}}_0\\ 0& \Vert b\Vert & {\tilde{c}}_1& {\tilde{d}}_1\\ 0& 0& \Vert c\Vert & {\stackrel{⌣}{d}}_2\\ 0& 0& 0& {\stackrel{⌣}{d}}_3\end{array}\right]$ ,

where $\Vert c\Vert =\sqrt{{\left|{\tilde{c}}_2\right|}^2+{\left|{\tilde{c}}_3\right|}^2}$ . The matrix of the transformation, or triangularization $X\to R$ is

$T=\left(1\oplus 1\oplus T_c\right)\left(1\oplus T_b\right)T_a.$ (18)

Each of these DsiHTs is unitary, and therefore this matrix T is unitary. The inverse matrix $Q=T^{-1}$ is also unitary and can be written as

$Q=T^{\prime }={T^{\prime }}_a\left(1\oplus {T^{\prime }}_b\right)\left(1\oplus 1\oplus {T^{\prime }}_c\right).$ (19)

Thus, we have an explicit representation of the matrix Q. Here, the operation A' denotes the conjugate transposition of a matrix A. Thus, $TX=R$ and we obtain the following decomposition of the matrix X:

$X=QR.$ (20)

It should be noted that if we apply instead of M-type DsiHT the transform of type T or G in the above example, the diagonal coefficients of the matrix R will be changed as follows. In the case of the T-type DsiHT,

$\Vert a\Vert \to \text{sign}\left(a_0\right)\Vert a\Vert ,\Vert b\Vert \to \text{sign}\left({\hat{b}}_1\right)\Vert b\Vert ,\Vert c\Vert \to \text{sign}\left({\tilde{c}}_2\right)\Vert c\Vert ,$

and in the case of the G-type DsiHT, these coefficients will be changed as

$\Vert a\Vert \to \text{sign}\left(a\right)\Vert a\Vert ,\Vert b\Vert \to \text{sign}\left(b\right)\Vert b\Vert ,\Vert c\Vert \to \text{sign}\left(c\right)\Vert c\Vert .$

Example 4 × 4: We consider the method of QR-decomposition that is similar to the method of the Householder transformations, only the DsiHTs will be used instead of the Householder transformations. First, we calculate the DsiHT by using the analytical equations, instead of matrix multiplications.

Let X be the following complex 4 × 4 matrix:

$X=\left[\begin{array}{cccc}1+2i& 2-3i& 3+4i& -3+1i\\ 2-3i& 3+i& 2-2i& -6-7i\\ 1-i& 2-4i& 3+2i& 1+2i\\ 3-i& 4+3i& 4-2i& 2+4i\end{array}\right].$

The method of QR decomposition of X with the DsiHTs results in the following presentations of the matrix $X=QR$ .

a) T-type DsiHT:

The matrix Q is

$Q_T=\left[\begin{array}{cccc}0.1826+0.3651i& 0.3448-0.6035i& -0.2415+0.1577i& -0.5158+0.0299i\\ 0.3651-0.5477i& 0.0771+0.1906i& 0.0032-0.4489i& -0.5682+0.0075i\\ 0.1826-0.1826i& 0.1407-0.5490i& -0.0966-0.5316i& 0.5457-0.1495i\\ 0.5477-0.1826i& 0.2859+0.2677i& -0.4710+0.4489i& 0.2990+0.0224i\end{array}\right]$

and the triangular matrix equals

$R_T=\left[\begin{array}{cccc}5.4772& 2.5560+2.7386i& 6.5727+0.5477i& 1.6432-1.4606i\\ 0& 7.3462& -1.6743+2.9403i& -2.7497+0.5763i\\ 0& 0& -3.3243& 3.6995-4.9272i\\ 0& 0& 0& 5.6893+6.0780i\end{array}\right].$

The first column of the matrix $Q_T$ is proportional to the first column of the matrix X,

$\left[\begin{array}{c}0.1826+0.3651i\\ 0.3651-0.5477i\\ 0.1826-0.1826i\\ 0.5477-0.1826i\end{array}\right]=0.1826\left[\begin{array}{c}1+2i\\ 2-3i\\ 1-i\\ 3-i\end{array}\right].$

b) M-type DsiHT

The matrix Q is

$Q_M=\left[\begin{array}{cccc}0.1826+0.3651i& 0.3448-0.6035i& 0.2415-0.1577i& -0.5166-0.0088i\\ 0.3651-0.5477i& 0.0771+0.1906i& -0.0032+0.4489i& -0.5671-0.0350i\\ 0.1826-0.1826i& 0.1407-0.5490i& 0.0966+0.5316i& 0.5554-0.1083i\\ 0.5477-0.1826i& 0.2859+0.2677i& 0.4710-0.4489i& 0.2999\end{array}\right]$

and the triangular matrix is

$R_M=\left[\begin{array}{cccc}5.4772& 2.5560+2.7386i& 6.5727+0.5477i& 1.6432-1.4606i\\ 0& 7.3462& -1.6743+2.9403i& -2.7497+0.5763i\\ 0& 0& +3.3243& -3.6995+4.9272i\\ 0& 0& 0& 6.1279+5.6355i\end{array}\right]\text{.}$

Up to the signs ±, many coefficients of the matrix $Q_M$ are equal to the coefficients of $Q_T$ , and the main difference in the 4th columns of these matrices. In the matrices $R_M$ and $R_T$ , the last coefficients are different, others are the same or differ only in the sign.

c) Householder Transforms

We consider for comparison the Householder transform decomposition $X=Q_H{R}_H$ . The Householder transformation [6] is defined as $H=I-2w{w}^{\prime }$ , where the normalized vector w is calculated

$w=x-{\left(\Vert x\Vert ,0,0,\cdots ,0\right)}^{\prime }/\sqrt{2\Vert x\Vert \left(\Vert x\Vert -x_0\right)}$

and $x={\left(x_0,x_1,x_2,\cdots ,x_{N-1}\right)}^{\prime }$ is a given vector. When running the MATLAB function “qr.m,” we obtain the following matrices:

$Q_H=\left[\begin{array}{cccc}-0.1826-0.3651i& -0.3448+0.6035i& 0.2415-0.1577i& 0.3743+0.3562i\\ -0.3651+0.5477i& -0.0771-0.1906i& -0.0032+0.4489i& 0.3937+0.4097i\\ -0.1826+0.1826i& -0.1407+0.5490i& 0.0966+0.5316i& -0.4821-0.2963i\\ -0.5477+0.1826i& -0.2859-0.2677i& 0.4710-0.4489i& -0.2207-0.2030i\end{array}\right]$

and

$R_H=\left[\begin{array}{cccc}-5.4772& -2.5560-2.7386i& -6.5727-0.5477i& -1.6432+1.4606i\\ 0& -7.3462& 1.6743-2.9403i& 2.7497-0.5763i\\ 0& 0& 3.3243& -3.6995+4.9272i\\ 0& 0& 0& -8.3252\end{array}\right]\text{.}$

The last column of the matrix $Q_H$ is different from the last columns of the matrices $Q_T$ and $Q_M$ , other coefficients are equal up to the sign. The same differences can be seen in the triangular matrices $R_H$ , $R_T$ , and $R_M$ .

d) G-type DsiHT:

The matrix Q is

$Q_G=\left[\begin{array}{cccc}0.4082& 0.2457-0.6502i& -0.2362-0.1656i& -0.5166-0.0088i\\ -0.3266-0.5715i& 0.1061+0.1761i& 0.4179-0.1639i& -0.5671-0.0350i\\ -0.0816-0.2449i& 0.0527-0.5643i& 0.4576-0.2872i& 0.5554-0.1083i\\ 0.0816-0.5715i& 0.3244+0.2195i& -0.5918-0.2705i& 0.2999\end{array}\right]$

and the triangular matrix is

$R_G=\left[\begin{array}{cccc}2.4495+4.8990i& -1.3064+3.5109i& 2.4495+6.1237i& 2.0412+0.8165i\\ 0& 7.2550+1.1542i& -2.1155+2.6407i& -2.8061+0.1371i\\ 0& 0& -1.2353+3.0863i& -3.1997-5.2656i\\ 0& 0& 0& 6.1279+5.6355i\end{array}\right].$

This decomposition is very different from the above three QR-decompositions. All coefficients of the first 3 columns of matrices $Q_G$ and $R_G$ differ from the coefficients of the corresponding matrices of the above decompositions by the T-and M-type, as well as the Householder QR decomposition. The last columns in matrices $Q_G$ and $Q_M$ are equal, as well as in matrices $R_G$ and $R_M$ .

Here, we want to mention that if we apply the strong DsiHTs starting from the last column of the matrix, we obtain the decomposition of the matrix $X=QL$ with the left triangular matrix. For the G-type strong DsiHT, the matrix Q is

$Q_G=\left[\begin{array}{cccc}0.6434& 0.1675-0.3605i& 0.5481-0.2101i& -0.0408+0.2858i\\ -0.1511-0.0403i& 0.1880+0.0742i& -0.1690-0.4448i& -0.8165+0.2041i\\ -0.6892+0.1466i& 0.2775-0.4503i& 0.3496-0.2445i& 0.2041\\ 0.1270+0.2211i& 0.4693+0.5487i& -0.0886-0.4891i& 0.4082\end{array}\right]$

and the left triangular matrix is

$L_G=\left[\begin{array}{cccc}-0.2137+1.5731i& 0& 0& 0\\ 1.1871-1.9594i& 7.9344-0.8122i& 0& 0\\ 1.9415+4.1538i& 0.6302+0.7221i& 2.5389+7.6166i& 0\\ -0.2858+1.0614i& -1.1431-1.4697i& 1.2247-0.2041i& 4.8990+9.7980i\end{array}\right].$

One can notice from this example that the QR-decomposition by the G-type DsiHTs differs much from the decomposition by the Householder transforms. The QR-decomposition by M-type DsiHTs is very similar to the Householder transform method. The M-type DsiHT is fast and can be implemented by using 2 × 2 basic transformations, as well by the analytical equations. To analyse the difference of these two decompositions in more detail, we consider the example with a 6 × 6 complex matrix X.

Example 6 × 6: Let the matrix X be the following:

$X=\left[\begin{array}{cccccc}1+2i& 2-3i& 3+4i& -3+i& -4-i& 2-3i\\ 2-3i& 3+i& 2-2i& -6-7i& 2+i& 5-2i\\ 4-i& 3-2i& 4-5i& 2+3i& 4+7i& 6+2i\\ 5+2i& 5+i& 3-2i& 8-3i& 7-2i& 2+3i\\ 4-3i& -5-2i& 1-i& 2-4i& 3+2i& 1+2i\\ 7-2i& 6+i& 3-i& 4+3i& 4+3i& 2+4i\end{array}\right].$

The QR-decomposition by the M-type DsiHTs results in the following matrices:

$\begin{array}{l}{Q}_M=\left[\begin{array}{cccccc}0.0839& 0.1419& 0.3046& -0.1235& 0.4129& -0.0136\\ 0.1678& 0.2321& 0.2051& -0.4530& 0.2174& 0.4402\\ 0.3357& 0.1232& 0.2883& -0.0854& 0.0096& -0.4182\\ 0.4196& 0.2579& -0.0885& 0.3133& 0.3378& -0.1404\\ 0.3357& -0.6763& -0.0301& -0.0356& 0.3404& -0.2840\\ 0.5874& 0.2937& -0.1343& 0.0922& -0.1331& 0.1813\end{array}\right]\\ +i\left[\begin{array}{cccccc}0.1678& -0.3926& 0.5185& -0.0103& -0.2061& 0.4476\\ -0.2518& 0.2579& 0.0226& -0.4400& 0.2949& -0.1367\\ -0.0839& -0.1275& -0.5164& 0.1108& 0.4122& 0.3669\\ 0.1678& 0.0430& -0.2965& -0.3644& -0.4614& -0.2323\\ -0.2518& -0.0330& 0.2352& 0.0055& 0.1455& -0.3004\\ -0.1678& 0.2465& 0.2758& 0.5705& -0.0318& 0\end{array}\right]\end{array}$

and

$\begin{array}{l}{R}_M=\left[\begin{array}{cccccc}11.9164& 5.5386& 6.9652& 7.4687& 6.1260& 4.5316\\ 0& 9.8295& 0.6133& -1.5246& 0.4542& 4.0665\\ 0& 0& 6.4709& -3.2862& -4.5013& 0.9395\\ 0& 0& 0& 11.9062& 1.6459& 0.0832\\ 0& 0& 0& 0& 6.3390& 2.3524\\ 0& 0& 0& 0& 0& -2.1708\end{array}\right]\\ +i\left[\begin{array}{cccccc}0& -0.8392& -2.8532& -1.9301& 2.8532& 6.0421\\ 0& 0& -0.3095& 1.0603& -4.2671& -0.3324\\ 0& 0& 0& 3.2384& 6.6643& 0.1439\\ 0& 0& 0& 0& -1.1619& 3.4811\\ 0& 0& 0& 0& 0& -3.1871\\ 0& 0& 0& 0& 0& -3.5886\end{array}\right].\end{array}$

The method of Householder transforms which is performed by the MATLAB function “qr.m” results in the following matrices $Q_H$ and $R_H$ in the QR-de- composition $X=Q_H{R}_H$ . In the matrix $Q_H$ , the last column differs from the same column in the matrix $Q_M$ , when using the M-type matrices in QR-decom- position. The remaining part, or the 6 × 5 sub-matrix of $Q_H$ differs from the same sub-matrix of $Q_M$ only by the sign. Thus, we can write the matrix $Q_H$ in the following way:

$Q_H=-{\left(Q_M\right)}_{6\times 5}$ ⨆ $\underset{}{\underset{︸}{\left[\begin{array}{c}-0.3900\\ 0.3448\\ -0.5304\\ 0.1261\\ 0.1100\\ 0.0939\end{array}\right]+i\left[\begin{array}{c}0.2201\\ 0.3059\\ -0.1679\\ -0.2404\\ -0.3985\\ 0.1552\end{array}\right]}}.$

All coefficients of the triangular matrix $R_H$ , except the last coefficient, equal to the corresponding coefficients of the matrix $R_M$ with the sign minus. In matrix $R_H$ , this coefficient equals −4.1941 and in the matrix $R_M$ such coefficient is 2.1708 + 3.5886. Therefore, we can write that

$R_H=-R_M+\left[\begin{array}{c}0\\ 0\\ 0\\ 0\\ 0\\ 4.1941-\left(2.1708+3.5886\right)\end{array}\right].$

5. The Scripts for the Decomposition by the DsiHT

Below are MATLAB-based codes for QR-decomposition of a complex square matrix X, by using the DsiHT. The function “amqr_compex.m” is for QR-de- composition of X by the DsiHT with the basic transforms T, M, and G. The Householder transform-based QR decomposition is calculated in this example by the MATLAB function “qr.” All matrices in the examples given in Section 4 were calculated by these codes.

The function amqr_complex is used to calculate the QR decomposition by the DsiHTs. The parameter “ntype” is selected as 1, 2, and 3 for the T, M, and G-type DsiHTs, respectively. If parameter “ntype” is set to 0, the M -type DsiHT is calculated by analytical Equations (4)-(6) in the function msob_enanalcomp. The calculation of 2 × 2 basic matrices of types T, M, and G are accomplished by the corresponding functions msob2T, msob2M, and msob2G in the main function msob_complexA that calculates the DsiHT. The scripts of all these functions are given below.

Below is the script of the function “msob_complex1sp.m” to compute the strong G-type DsiHT. To calculate the strong T and M-types DsiHT, the corresponding function can be written in a similar way.

6. Mixed Type DsiHT QR Decomposition

It is clear that on different stages of QR-decomposition by the DsiHT, we can change the type of the DsiHT. Such mixed type QR-decompositions can be considered and applied in practice together with the described above QR-decom- positions by the T, M, and G-type DsiHTs.

As an example, we consider the matrix X given in Example 6 × 6 in Section 4 with the following set of types of transforms: [T M G T T], or [1 2 3 1 1] in numbers when running the codes. It means that the first transform which will be used to obtain the first heap in the first column of in the matrix X is the T-type DsiHT. The second transform is the M-type DsiHT to get the second heap in the matrix, or coefficient number (2, 2) in the triangular matrix R, and so on. As a result, we obtain the decomposition of the matrix $X=Q_{12311}{R}_{12311}$ , where the unitary matrix is

$\begin{array}{l}{Q}_{12311}=\left[\begin{array}{cccccc}0.0839& 0.1419& -0.5953& -0.1235& -0.4129& 0.3665\\ 0.1678& 0.2321& -0.0986& -0.4530& -0.2174& 0.1278\\ 0.3357& 0.1232& 0.3685& -0.0854& -0.0096& 0.0767\\ 0.4196& 0.2579& 0.3079& 0.3133& -0.3378& -0.2713\\ 0.3357& -0.6763& -0.2063& -0.0356& -0.3404& -0.4070\\ 0.5874& 0.2937& -0.2043& 0.0922& 0.1331& 0.0997\end{array}\right]\\ +i\left[\begin{array}{cccccc}0.1678& -0.3926& 0.0853& -0.0103& 0.2061& 0.2573\\ -0.2518& 0.2579& 0.1812& -0.4400& -0.2949& -0.4429\\ -0.0839& -0.1275& 0.4625& 0.1108& -0.4122& 0.5510\\ 0.1678& 0.0430& 0.0305& -0.3644& 0.4614& -0.0103\\ -0.2518& -0.0330& -0.1170& 0.0055& -0.1455& 0.0722\\ -0.1678& 0.2465& -0.2289& 0.5705& 0.0318& -0.1515\end{array}\right].\end{array}$

When comparing with the QR-decomposition by the M-type DsiHT, one can notice that the columns number 3 and 6 and the sign on the 5^th column are different in matrices $Q_{12311}$ and $Q_M$ . The triangular matrix equals to

$\begin{array}{l}{R}_{12311}=\left[\begin{array}{cccccc}11.9164& 5.5386& 6.9652& 7.4687& 6.1260& 4.5316\\ 0& 9.8295& 0.6133& -1.5246& 0.4542& 4.0665\\ 0& 0& -2.4534& 4.2425& 7.8733& -0.2230\\ 0& 0& 0& 11.9062& 1.6459& 0.0832\\ 0& 0& 0& 0& 6.3390& -2.3524\\ 0& 0& 0& 0& 0& 1.8050\end{array}\right]\\ +i\left[\begin{array}{cccccc}0& -0.8392& -2.8532& -1.9301& 2.8532& 6.0421\\ 0& 0& -0.3095& 1.0603& -4.2671& -0.3324\\ 0& 0& -5.9878& 1.8131& 1.6386& -0.9239\\ 0& 0& 0& 0& -1.1619& 3.4811\\ 0& 0& 0& 0& 0& 3.1871\\ 0& 0& 0& 0& 0& -3.7858\end{array}\right].\end{array}$

In this matrix, the coefficients of the 3^rd and 6^th rows and the sign in 5^th row differ from the corresponding coefficients of matrix $R_M$ .

It should be noted that instead of combination of types [1 2 3 1 1], we can use other combinations with 1, 2, and 3. The number of such combinations is 3⁵ = 243. In general case of the N × N matrix, we can choose one combination of with numbers presenting the types of the DsiHT. The number of such combinations equals $3^{\left(N-1\right)}$ and they can be used for calculating the QR-decomposition by the DsiHTs. The combinations with all 1s, 2s, and 3s correspond to the QR-decom- positions by the T, G, and M-type DsiHTs. Also, different paths can be used for the DsiHT, which increases the number of possible QR decompositions.

In conclusion, we consider a few QR-decompositions which were calculated for the pseudorandom integer N × N matrices X with complex coefficients with real and imaginary parts in the range 1:N. For that, the MATLAB function “randi.m” is used. Twelve values of N were arbitrary chosen to be 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400. The QR-decompositions for each of these values of N were calculated by the M-type DsiHT and the Householder transforms; the script of the code is given below for the QR decomposition of the random complex 400 × 400 matrix.

7. Summary Results

To compare the results of the QR-decomposition, the precision of computation was estimated by the 2-norms of the matrix ${\Delta }_M=X-Q_M{R}_M$ and matrix ${\Delta }_H=X-Q_H{R}_H$ , by using the MATLAB function “norm.m.” The results of estimations are given in Table 1.

Table 1. The precision of the QR-decomposition by the M-type DsiHT and Householder transforms.

One can notice that in most cases the 2-norm of the QR-decomposition by the M-type DsiHTs is less than the same norm when using the Householder transforms.

8. Conclusion

We described three different types of QR-decompositions that include the DsiHT with T, G, and M-type complex matrices. The decomposition by analytical formulas was also given for the M-type DsiHT. The mixed type QR-decomposition, when different type DsiHTs are used in different stages of the algorithm was also presented. For an N × N complex nonsingular matrix, the number of such decompositions is greater than $3^{\left(N-1\right)}$ . Examples of the QR-decomposition were given in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the Householder transform-based QR-decomposition. MATLAB-based scripts of the codes for calculating the DsiHTs and QR decompositions are given. The different QL-decompositions of a complex matrix can be obtained in a similar way. We believe that the concept of the DsiHT can be generalized to the quaternion space [20] and the QR-decomposition of the quaternion matrix can be calculated and used together with the known methods of decompositions [19] .

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Morrison, D.D. (1960) Remarks on the Unitary Triangularization of a Nonsymmetric Matrix. Journal ACM, 7, 185-186. https://doi.org/10.1145/321021.321030
[2]	Businger, P. and Golub, G.H. (2017) Linear Least Squares Solutions by Householder Transformations. In: Bauer, F.L., Ed., Linear Algebra, Handbook for Automatic Computation, Vol. 2, Springer, Berlin.
[3]	Horn, R.A. and Charles, R.J. (1985) Matrix Analysis. Cambridge University Press, Cambridge.
[4]	Golub, G.H. and Van Loan, C.F. (1996) Matrix Computations. 3rd Edition, Johns Hopkins, Baltimore.
[5]	Anderson, E., Bai, Z., Bischof, C.H., et al. (1999) LAPACK Users’ Guide. 3rd Edition, SIAM, Philadelphia. https://doi.org/10.1137/1.9780898719604
[6]	Moon, T.K. and Stirling, W.C. (2000) Mathematical Methods and Algorithms for Signal Processing. Prentice Hall, Hoboken.
[7]	Alonso, P., Peña, J.M. and Serrano, M.L. (2017) QR Decomposition of Almost Strictly Sign Regular Matrices. Journal of Computational and Applied Mathematics, 318, 646-657. https://doi.org/10.1016/j.cam.2015.10.030
[8]	Björck, A. (1967) Solving Linear Least Squares Problems by Gram-Schmidt Orthogonalization. BIT Numerical Mathematics, 7, 1-21. https://doi.org/10.1007/BF01934122
[9]	Rutishause, H. (2017) Simultaneous Iteration Method for Symmetric Matrices. In: In: Bauer, F.L., Ed., Linear Algebra, Handbook for Automatic Computation, Vol. 186, Springer, Berlin.
[10]	Householder, A.S. (1958) Unitary Triangulation of a Nonsymmetric Matrix. Journal ACM, 5, 339-342. https://doi.org/10.1145/320941.320947
[11]	Bindel, D., Demmel, J., Kahan, W. and Marques, O. (2001) On Computing Givens Rotations Reliably and Efficiently. LAPACK Working Note 148, University of Tennessee, Knoxville, UT-CS-00-449.
[12]	Demmel, J., Grigori, L., Hoemmen, M. and Langou, J. (2012) Communication-Optimal Parallel and Sequential QR and LU Factorizations. SIAM Journal on Scientific Computing, 34, 206-239. https://doi.org/10.1137/080731992
[13]	Grigoryan, A.M. and Grigoryan, M.M. (2006) Nonlinear Approach of Construction of Fast Unitary Transforms. Proceedings of the 40th Annual Conference on Information Sciences and Systems (CISS 2006), Princeton University, Princeton, 1073-1078. https://doi.org/10.1109/CISS.2006.286625
[14]	Grigoryan, A.M. and Grigoryan, M.M. (2007) Discrete Unitary Transforms Generated by Moving Waves. Proceedings of SPIE, 6701, Article ID: 670125. https://doi.org/10.1117/12.728383
[15]	Grigoryan, A.M. and Grigoryan, M.M. (2007) New Discrete Unitary Haar-Type Heap Transforms. Proceedings of SPIE, 6701, Article ID: 670126. https://doi.org/10.1117/12.728386
[16]	Grigoryan, A.M. and Grigoryan, M.M. (2009) Brief Notes in Advanced DSP: Fourier Analysis with MATLAB. CRC Press, Taylor and Francis Group, Boca Raton.
[17]	Grigoryan, A.M. (2014) New Method of Givens Rotations for Triangularization of Square Matrices. Journal of Advances in Linear Algebra & Matrix Theory (ALAMT), 4, 65-78. https://doi.org/10.4236/alamt.2014.42004
[18]	Grigoryan, A.M. (2015) Fast Heap Transform-Based QR-Decomposition of Real and Complex Matrices: Algorithms and Codes, [9411-21]. Proceedings of SPIE, 9411, 94110N. https://doi.org/10.1117/12.2083404
[19]	Li, Y., Wei, M.S., Zhang, F.X. and Zhao, J.L. (2016) Real Structure-Preserving Algorithms of Householder Based Transformations for Quaternion Matrices. Journal of Computational and Applied Mathematics, 305, 82-91. https://doi.org/10.1016/j.cam.2016.03.031
[20]	Grigoryan, A.M. and Agaian, S.S. (2018) Quaternion and Octonion Color Image Processing with MATLAB. Vol. PM279, SPIE, Bellingham, 404. https://doi.org/10.1117/3.2278810