ABSTRACT

We present explicit inverses of two Brownian-type matrices, which are defined as Hadamard products of certain already known matrices. The matrices under consideration are defined by 3n − 1 parameters and their lower Hessenberg form inverses are expressed analytically in terms of these parameters. Such matrices are useful in the theory of digital signal processing and in testing matrix inversion algorithms.

1. Introduction

Brownian matrices are frequently involved in problems concerning “digital signal processing”. In particular, Brownian motion is one of the most common linear models used for representing nonstationary signals. The covariance matrix of a discrete-time Brownian motion has, in turn, a very characteristic structure, the so-called “Brownian matrix”.

In [1] (Equation (2)) the explicit inverse of a class of matrices with elements

(1)

is given. On the other hand, the analytic expressions of the inverses of two symmetric matrices and, where

(2)

respectively, are presented in [2] (first equation in p. 113, and Equation (1), respectively). The matrix K is a special case of Brownian matrix and is a lower Brownian matrix, as they have been defined in [3] (Equation (2.1)). Earlier, in [4] (paragraph following Equation (3.3)) the term “pure Brownian matrix” for the type of the matrix K has introduced. Furthermore, in [5] (discussion concerning Equations (28)-(30)) the so-called “diagonal innovation matrices” (DIM) have been treated, special cases of which are the matrices K and N.

In the present paper, we consider two matrices A₁ and A₂ defined by

(3)

where the symbol denotes the Hadamard product. Hence, the matrices have the forms

(4)

and

(5)

Let us now define for a matrix the terms “pure upper Brownian matrix” and “pure lower Brownian matrix”, for the elements of which the following relations are respectively valid

(6)

The matrix A₁ (Equation (4)) is a lower Brownian matrix. Furthermore, the matrix PNP, where is the permutation matrix with elements

(7)

is a pure Brownian matrix and a pure lower Brownian matrix. Hence, their Hadamard product gives a pure lower Brownian matrix, that is, the matrix.

In the following sections, we deduce in analytic form the inverses and determinants of the matrices A₁ and A₂; and we study the numerical complexity on evaluating and.

2. The Inverse and Determinant of A₁

The inverse of A₁ is a lower Hessenberg matrix expressed analytically by the 3n − 1 parameters defining A₁. In particular, the inverse has elements given by the relations

(8)

where

(9)

with

(10)

and with the obvious assumptions

(11)

To prove that the relations (8)-(10) give the inverse matrix, we reduce A₁ to the identity matrix I by applying a number of elementary row transformations.

Then the product of the corresponding elementary matrices gives the inverse matrix of A₁. These transformations are defined by the following sequence of row operations.

Operation 1 (applied on A₁ and on the identity matrix I):

which transforms A₁ into the lower triangular matrix C₁ given by

and the identity matrix I into the upper bidiagonal matrix F₁ with main diagonal

and upper first diagonal

Operation 2 (applied on and):

which derives a lower bidiagonal matrix with main diagonal

and lower first diagonal

while the matrix is transformed into the tridiagonal matrix given by

Operation 3 (applied on and):

which derives the diagonal matrix

and, respectively, the lower Hessenberg matrix F₃ given by

with the symbol s standing for the quantity.

Operation 4 (applied on and):

which transforms into the identity matrix I and the matrix into the inverse.

The determinant of takes the form

(12)

Evidently, is singular if or, considering the relation (9), if for some.

3. The Inverse and Determinant of A₂

In the case of, its inverse is a lower Hessenberg matrix with elements given by the relations

(13)

where

(14)

with

(15)

and with the obvious assumptions

(16)

In order to prove that the relations (13)-(15) give the inverse matrix, we follow a similar manner to that of Section 2.

Operation 1 (applied on A₂ and on the identity matrix I):

which transforms A₂ into the lower triangular matrix equal to

and the identity matrix I into the bidiagonal matrix with main diagonal

and upper first diagonal

Operation 2 (applied on and):

which derives the lower bidiagonal matrix D₂ with main diagonal

and lower first diagonal

while the matrix is transformed into the tridiagonal matrix with main diagonal

upper first diagonal

and lower first diagonal

Operation 3 (applied on and):

with, which yields the diagonal matrix,

and the lower Hessenberg matrix equal to

where the symbol stands for.

Operation 4 (applied on and):

which transforms into the identity matrix I and into the inverse.

The determinant of has the form

(17)

which shows in turn that the matrix is singular if, or, adopting the conventions (14), if for some.

4. Numerical Complexity

The relations (8) and (13) lead to recurrence formulae, by which the inverses and, respectively, are computed in multiplications/divisions and additions/substractions. In fact, the recursive algorithm

(18)

(19)

(20)

(21)

where, , , and are given by the relation (9), computes in mult/div (since the coefficients of depends only on the second subscript) and add/sub.

In terms of, the above algorithm takes the form

For the computation of the algorithms (18)-(21) changes only in the estimation of the diagonal elements, for which we have

where, , , and are given by the relation (14). Therefore, considering the relations (9) and (14), it is clear that the number of mult/div and add/sub in computing is the same with that of.

5. Concluding Remarks

The matrices A₁ and A₂ represent generalizations of known classes of test matrices. For instance, the test matrices given in [6] (Equations (2.1) and (2.2)) and in [1] (Eq. (2)) belong to the categories presented. Furthermore, by restricting the a’s and b’s to unity, A₁ and A₂ reduce to the matrices given in [2]. Also, the matrices in [7] (pp. 41, 42, 49) are special cases of A₁ and A₂. On the other hand, concerning the recursive algorithms given in Section 4, we have performed numerical experiments by assigning random values to the parameters of A₁, and with a variety of the order n from 256 to 1024. We have found that computing by the recursive algorithms (18)-(21) is ~100 times faster than using the LU decomposition when n = 256 and increases gradually to ~1000 times faster when n = 1024.

REFERENCES