ON TWO BROWNIAN--TYPE MATRICES WITH\\ EXPLICIT HESSENBERG INVERSES
F. N. Valvi
In this paper, we present explicit inverses for 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 the theory and applications of test matrices, i.e., matrices with known explicit inverses, which are thus appropriate for testing matrix inversion algorithms.
math0208075.tex
\documentclass[12pt,preprint,flushrt]{aastex}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{natbib}

\shortauthors{Valvi and Geroyannis}
\shorttitle{BROWNIAN MATRICES WITH EXPLICIT HESSENBERG INVERSES}

\begin{document}



\title{ON TWO BROWNIAN--TYPE MATRICES WITH\\
       EXPLICIT HESSENBERG INVERSES}

\author{F. N. Valvi}
\affil{Department of Mathematics, University of Patras, Greece} 

\author{V. S. Geroyannis}
\affil{Department of Physics, University of Patras, Greece}

\begin{abstract}
In this paper, we present explicit inverses for 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 the theory and applications of test matrices, i.e., matrices with known explicit inverses, which are thus appropriate for testing matrix inversion algorithms.   
\end{abstract}

\keywords{Brownian matrix --- explicit inverse --- Hadamard product --- Hessenberg matrix --- numerical complexity --- test matrix}


\section{Introduction}
\citet{her69} gives the explicit inverse of a matrix $G_n = [\beta_{ij}]$ with elements
\begin{displaymath}
\beta_{ij} = \left\{ \begin{array}{ll} b_j, & \ \ i \leqslant j, \\
                                       a_j, & \ \ i > j.
                     \end{array}
             \right.
\end{displaymath}
\citet{val77} gives the explicit inverses of two symmetric matrices $K = [\kappa_{ij}]$ and $N = [\nu_{ij}]$ with elements
\begin{displaymath}
\kappa_{ij} = k_i \ \ \ \textrm{and} \ \ \ \nu_{ij} = k_j, \ \ i \leqslant j,
\end{displaymath}  
respectively. $K$ is a special case of Brownian--type matrix and $G_n$ is a lower Brownian matrix as defined in \citet{gba86}. Earlier, \citet{pic83} has used the term ``pure Brownian matrix'' for the type of the matrix $K$; and \citet{ckm82} have treated the so-called ``diagonal innovation matrices'' (DIM), special cases of which are the matrices $K$ and $N$.  

In the present paper, we consider two matrices $A_1$ and $A_2$ defined by 
\begin{displaymath}
A_1 = K \circ G_n \ \ \ \textrm{and} \ \ \ A_2 = N \circ G_n,
\end{displaymath}
where the symbol $\circ$ denotes the Hadamard product. These matrices have the explicit forms
\begin{equation}
A_1 = \left[
      \begin{array}{cccccc}
             k_1 b_1 & k_1 b_2 & k_1 b_3 & \ldots & k_1 b_{n-1}     & k_1 b_n     \\
             k_1 a_1 & k_2 b_2 & k_2 b_3 & \ldots & k_2 b_{n-1}     & k_2 b_n     \\
             k_1 a_1 & k_2 a_2 & k_3 b_3 & \ldots & k_3 b_{n-1}     & k_3 b_n     \\
             \ldots  &         &         &        &                 &             \\
             \ \ k_1 a_1 \ \ & \ \ k_2 a_2 \ \ & \ \ k_3 a_3 \ \ & \ \ \ldots \ \ & \ \ k_{n-1} b_{n-1} \ \ & \ \ k_{n-1} b_n \ \    \\
             k_1 a_1 & k_2 a_2 & k_3 a_3 & \ldots & k_{n-1} a_{n-1} & k_n b_n
      \end{array}
      \right]
\end{equation} 
and
\begin{equation}
A_2 = \left[
      \begin{array}{cccccc}
             k_1 b_1 & k_2 b_2 & k_3 b_3 & \ldots & k_{n-1} b_{n-1}     & k_n b_n         \\
             k_2 a_1 & k_2 b_2 & k_3 b_3 & \ldots & k_{n-1} b_{n-1}     & k_n b_n         \\
             k_3 a_1 & k_3 a_2 & k_3 b_3 & \ldots & k_{n-1} b_{n-1}     & k_n b_n         \\
             \ldots  &         &         &        &                     &                 \\
             \ \ k_{n-1} a_1 \ \ & \ \ k_{n-1} a_2 \ \ & \ \ k_{n-1} a_3 \ \ & \ \ \ldots \ \ & \ \ k_{n-1} b_{n-1} \ \ & \ \ k_n b_n \ \ \\
             k_n a_1     & k_n a_2     & k_n a_3     & \ldots & k_n a_{n-1}     & k_n b_n
      \end{array}
      \right].
\end{equation}

In the following sections, we give the explicit inverses and determinants of these matrices.

\section{The Inverse and Determinant of $A_1$}
\subsection{The Inverse}
The inverse of $A_1$ is a lower Hessenberg matrix expressed analytically by the $3n-1$ parameters defining $A_1$. In particular, the inverse $A_1^{-1} = [\alpha_{ij}]$ of $A_1$ has elements given by the relations
\begin{equation}
\alpha_{ij} = \left\{ 
              \begin{array}{ll} 
              \frac{\displaystyle k_{i+1} b_{i-1} - k_{i-1} a_{i-1}}{\displaystyle c_{i-1} c_i}, & \ \ \ i = j \neq 1,n, \\
                                                                     &                       \\
              \frac{\displaystyle k_2}{\displaystyle k_1 c_1}, & \ \ \ i = j = 1,                                        \\
                                                                     &                       \\
              \frac{\displaystyle b_{n-1}}{\displaystyle c_{n-1} c_n}, & \ \ \ i = j = n,                                \\
                                                                     &                       \\
              (-1)^{i+j} \frac{\displaystyle d_{j-1} g_i \prod_{\nu=j+1}^{i-1} k_{\nu} f_{\nu}}
                              {\displaystyle \prod_{\nu=j-1}^i c_{\nu}} \ , 
                                                           & \ \ \ i - j \geqslant 1,        \\
                                                                     &                       \\
              - \ \frac{\displaystyle 1}{\displaystyle c_i}, & \ \ \ j - i = 1,                                          \\
                                                                     &                       \\
              0, & \ \ \ j - i > 1,
              \end{array}
              \right.    
\end{equation}
where 
\begin{equation}
\left\{
\begin{array}{llll}
c_i = k_{i+1} b_i - k_i a_i,                 & \ \ i = 1,2,\ldots,n-1, & \ \ c_0 =1,     & \ \ c_n = b_n,
\\
d_i = k_{i+1} a_{i+1} b_i  - k_i a_i b_{i+1}, & \ \ i = 1,2,\ldots,n-2, & \ \ d_0 = a_1, &
\\
f_i = a_i - b_i,                             & \ \ i=2,3,\ldots,n-1,   &                 &
\\
g_i = k_{i+1} - k_i,                         & \ \ i=2,3,\ldots,n-1,   & \ \ g_n = 1,    &
\end{array}
\right.
\end{equation}
with 
\begin{equation}
\prod_{\nu=j+1}^{i-1} k_{\nu} f_{\nu} = 1 \ \ \ \textrm{if} \ \ \ i = j + 1,
\end{equation}
and with the obvious assumptions
\begin{equation}
k_1 \neq 0 \ \ \ \ \textrm{and} \ \ \ \ c_i \neq 0, \ \ \ i=1,2,\ldots,n.
\end{equation}

\subsection{The Proof}
In order to prove that the relations (3) give the inverse matrix $A_1^{-1}$, we shall reduce $A_1$ to the identity matrix by applying elementary row operations. Then the product of the corresponding elementary matrices gives the inverse matrix. In particular, we apply the following sequence of row operations. \\
\leftline{ }

Operation 1. $\textrm{row} \ i - \frac{k_i}{k_{i+1}} \times \textrm{row} \ (i+1), \ \ i=1,2,\ldots,n-1,$ \\
\leftline{ }
which gives the lower triangular matrix
\begin{equation*}
\left[ \begin{array}{llllll}
       \frac{k_1}{k_2} \left( k_2 b_1 - k_1 a_1 \right) & 0 & 0 & \ldots & 0 & 0 \\
       & & & & &                                                                 \\
       \frac{k_1 a_1}{k_3} \left( k_3 - k_2 \right) & \frac{k_2}{k_3} \left( k_3 b_2 - k_2 a_2 \right)
                                                            & 0 & \ldots & 0 & 0 \\
       & & & & &                                                                 \\
       \frac{k_1 a_1}{k_4} \left( k_4 -k_3 \right) & \frac{k_2 a_2}{k_4} \left( k_4 -k_3 \right) 
             & \frac{k_3}{k_4} \left( k_4 b_3 - k_3 a_3 \right) & \ldots & 0 & 0 \\
       & & & & &                                                                 \\
       \ldots & & & & &                                                          \\
       & & & & &                                                                 \\
       \frac{k_1 a_1}{k_n} \left( k_n - k_{n-1} \right) & \frac{k_2 a_2}{k_n} \left( k_n - k_{n-1} \right) &
       \frac{k_3 a_3}{k_n} \left( k_n - k_{n-1} \right) & \ldots & \frac{k_{n-1}}{k_n} \left( k_n b_{n-1} - k_{n-1} a_{n-1}
       \right) & 0                                                               \\
       & & & & &                                                                 \\
       k_1 a_1 & k_2 a_2 & k_3 a_3 & \ldots & k_{n-1} a_{n-1} & k_n b_n
       \end{array}
       \right].
\end{equation*} \\
\leftline{ }

Operation 2. $\textrm{row} \ i - \ \frac{k_i g_i}{k_{i+1} g_{i-1}} \ \times
              \textrm{row} \ (i-1), \ \ i=n,n-1,\ldots,3, \ \ \ k_{n+1} = 1,$ \\
\leftline{ }
which results in a bidiagonal matrix with main diagonal 
\begin{displaymath}
\left( \frac{k_1 c_1}{k_2} \ , \ \frac{k_2 c_2}{k_3} \ , \ \ldots \ , \ \frac{k_{n-1} c_{n-1}}{k_n} \ , \ k_n c_n
\right)
\end{displaymath}
and lower first diagonal
\begin{displaymath}
\left( 
\frac{k_1 a_1 g_2}{k_3} \ , \ \frac{k_2 k_3 g_3 f_2}{k_4 g_2} \ , \ \ldots \ , \ \frac{k_{n-2} k_{n-1} g_{n-1} f_{n-2}}{k_n g_{n-2}} \ , \ \frac{k_{n-1} k_n f_{n-1}}{g_{n-1}}
\right).
\end{displaymath} \\
\leftline{ }

Operation 3. $\textrm{row} \ 2 - \ \frac{k_2 a_1 g_2}{k_3 c_1} \ \times \textrm{row} \ 1, \ \ \ \ \textrm{and}$ 

   $\textrm{~~~~~~~~~~~~~~~~~~row} \ i -  
    k_i \ \frac{k_i g_i f_{i-1}}{k_{i+1} g_{i-1} c_{i-1}} \ \times 
    \textrm{row} \ (i-1), \ \ i=3,4,\ldots,n,$ \\ 
\leftline{ }
which gives the diagonal matrix 
\begin{displaymath}
\left\lceil \frac{k_1 c_1}{k_2} \ \ \ \frac{k_2 c_2}{k_3} \ \ \ \ldots \ \ \ \frac{k_{n-1} c_{n-1}}{k_n} \ \ \ k_n c_n \right\rfloor .
\end{displaymath} \\
\leftline{ }

Operation 4. $\frac{k_{i+1}}{k_i c_i} \times \textrm{row} \ i, \ \ i=1,2,\ldots,n,$ \\
\leftline{ }
which gives the identity matrix. \\
\leftline{ }

Operations 1--4 transform the identity matrix to the following forms, respectively. \\
\leftline{ }

Form 1. The upper bidiagonal matrix consisting of the main diagonal
\begin{displaymath}
\left( 1 \ , \ 1 \ , \ \ldots \ , \ 1 \right)
\end{displaymath}
and the upper first diagonal
\begin{displaymath}
\left( -\frac{k_1}{k_2} \ , \ -\frac{k_2}{k_3} \ , \ \ldots \ , \ -\frac{k_{n-1}}{k_n} \right).
\end{displaymath}

Form 2. The tridiagonal matrix
\begin{displaymath}
\left[
\begin{array}{cccccc} 
       1 & -\frac{k_1}{k_2} & 0 & \ldots & 0 & 0 \\
       0 & 1 & -\frac{k_2}{k_3} & \ldots & 0 & 0 \\
       \ \ 0 \ \ & \ \ -\frac{k_3 g_3}{k_4 g_2} \ \ & \ \ 1+\frac{k_2 g_3}{k_4 g_2} \ \ & \ \ \ldots \ \ & \ \ 0 \ \ & \ \ 0 \ \ \\
       \ldots & & & & &  \\
       \ \ 0 \ \ & \ \ 0 \ \ & \ \ 0 \ \ & \ \ \ldots \ \ & \ \ 1+\frac{k_{n-2} g_{n-1}}{k_n g_{n-2}} \ \ & \ \ -\frac{k_{n-1}}{k_n} \ \ \\
       0 & 0 & 0 & \ldots & -\frac{k_n}{g_{n-1}} & 1+\frac{k_{n-1}}{g_{n-1}} 
\end{array}
\right].
\end{displaymath}  

Form 3. The lower Hessenberg matrix
\begin{displaymath}
\left[
\begin{array}{ccccc}
       1 & -\frac{k_1}{k_2} & \ldots & 0 & 0                                                              \\
       -\frac{a_1 g_2 k_2}{k_3 c_0 c_1} & \frac{k_2}{k_3 c_1} \left( k_3 b_1 - k_1 a_1 \right) & 
                                                                                \ldots & 0 & 0            \\
       \frac{a_1 g_3 k_3 k_2 f_2}{k_4 c_0 c_1 c_2} & -\frac{d_1 g_3 k_3}{k_4 c_1 c_2} & \ldots & 0 & 0    \\
       \ldots & & & &                                                                                     \\
       s \frac{a_1 g_{n-1} k_{n-1} k_2 f_2 \ldots k_{n-2} f_{n-2}}{k_n c_0 c_1 \ldots c_{n-2}} &
       s \frac{d_1 g_{n-1} k_{n-1} k_3 f_3 \ldots k_{n-2} f_{n-2}}{k_n c_1 c_2 \ldots c_{n-2}} & \ldots &
       \frac{k_{n-1}}{k_n c_{n-2}} \left( k_n b_{n-2} - k_{n-2} a_{n-2} \right) & - \frac{k_{n-1}}{k_n}   \\
       s \frac{a_1 g_n k_n k_2 f_2 \ldots k_{n-1} f_{n-1}}{c_0 c_1 \ldots c_{n-1}} & 
       s \frac{d_1 g_n k_n k_3 f_3 \ldots k_{n-1} f_{n-1}}{c_1 c_2 \ldots c_{n-1}} & \ldots &
       -\frac{d_{n-2} k_n}{c_{n-2} c_{n-1}} & \frac{b_{n-1} k_n}{c_{n-1}}
\end{array}
\right],
\end{displaymath}
where the symbol $s$ stands for the quantity $(-1)^{i+j}$. \\
\leftline{ }

Form 4. The matrix whose the elements are given by the expressions (3).

\subsection{The Determinant}       
The determinant of $A_1$ takes the form 
\begin{equation}
\textrm{det}\left(A_1\right) = k_1 b_n \left( k_2 b_1 - k_1 a_1 \right)
            \left( k_3 b_2 - k_2 a_2 \right) \ \ldots \ 
            \left( k_n b_{n-1} - k_{n-1} a_{n-1} \right).
\end{equation}
Evidently, $A_1$ is singular if $k_1 = 0$ or, using the relations (4), $c_i = 0$ for some $i \in \left\{ 1,2,\ldots,n \right\}$. 

\section{The Inverse and Determinant of $A_2$}
\subsection{The Inverse}
In the case of $A_2$, its inverse $A_2^{-1} = [\alpha_{ij}]$ is a lower Hessenberg matrix with elements given by the relations 
\begin{equation}
\alpha_{ij} = \left\{ 
              \begin{array}{ll} 
              \frac{\displaystyle k_{i-1} b_{i-1} - k_{i+1} a_{i-1}}
                   {\displaystyle c_{i-1} c_i}, & \ \ \ i = j \neq 1,n,                      \\
                                                                     &                       \\
              \frac{\displaystyle 1}{\displaystyle c_1}, & \ \ \ i = j = 1,                  \\
                                                                     &                       \\
              \frac{\displaystyle k_{n-1} b_{n-1}}
                   {\displaystyle k_n c_{n-1} c_n}, & \ \ \                i = j = n,        \\
                                                                     &                       \\
              (-1)^{i+j} \frac{\displaystyle d_{j-1} g_i \prod_{\nu=j+1}^{i-1} k_{\nu} f_{\nu}}
                              {\displaystyle \prod_{\nu=j-1}^i c_{\nu}}, 
                                                           & \ \ \ i - j \geqslant 1,        \\
                                                                     &                       \\
              - \ \frac{\displaystyle 1}{\displaystyle c_i}, & \ \ \ j - i = 1,              \\
                                                                     &                       \\
              0, & \ \ \ j - i > 1,
              \end{array}
              \right.    
\end{equation}
where 
\begin{equation}
\left\{
\begin{array}{llll}
c_i = k_i b_i - k_{i+1} a_i,                 & \ \ i = 1,2,\ldots,n-1, & \ \ c_0 =1,    & \ \ c_n = b_n,
\\
d_i = k_i a_{i+1} b_i - k_{i+1} a_i b_{i+1}, & \ \ i = 1,2,\ldots,n-2, & \ \ d_0 = a_1, &
\\
f_i = a_i - b_i,                             & \ \ i=2,3,\ldots,n-1,   &                &
\\
g_i = k_i - k_{i+1},                         & \ \ i=2,3,\ldots,n-1,   & \ \ g_n = 1,   & 
\end{array}
\right.
\end{equation}
with
\begin{equation}
\prod_{\nu=j+1}^{i-1} k_{\nu} f_{\nu} = 1 \ \ \ \textrm{if} \ \ \ i = j + 1,
\end{equation}
and with the obvious assumptions
\begin{equation}
k_n \neq 0 \ \ \ \ \textrm{and} \ \ \ \ c_i \neq 0, \ \ \ i=1,2,\ldots,n.
\end{equation}

\subsection{The Proof}
In order to prove that the relations (8) give the inverse matrix $A_2^{-1}$, we shall reduce $A_2$ to the identity matrix by applying elementary row operations. Then the product of the corresponding elementary matrices gives the inverse matrix. In the present case, we carry out the following row operations. \\
\leftline{ }

Operation 1. $\textrm{row} \ i - \textrm{row} \ (i+1), \ \ \ i = 1,2,\ldots,n-1,$ \\
\leftline{ }
which gives the lower triangular matrix 
\begin{equation*}
\left[
\begin{array}{ccccc}
       k_1 b_1 - k_2 a_1 & 0 & \ldots & 0 & 0 \\
       a_1 \left( k_2 - k_3 \right) & k_2 b_2 - k_3 a_2 & \ldots & 0 & 0 \\
       \ldots & & & &  \\
       \ \ a_1 \left( k_{n-1} - k_n \right) \ \ & \ \ a_2 \left( k_{n-1} - k_n \right) \ \ & \ \ \ldots \ \ & 
       \ \ k_{n-1} b_{n-1} - k_n a_{n-1} \ \ & \ \ 0 \ \ \\
       k_n a_1 & k_n a_2 & \ldots & k_n a_{n-1} & k_n b_n
\end{array}
\right].
\end{equation*} \\
\leftline{ }

Operation 2. $\textrm{row} \ n - \frac{k_n}{g_{n-1}} \times \textrm{row} \ (n-1) \ \ \ \ \textrm{and}$ 

   $\textrm{~~~~~~~~~~~~~~~~~~row} \ i - \frac{g_i}{g_{i-1}} \times \textrm{row} \ (i-1), \ \ \ i=n-1,n-2,\ldots,3,$ \\
\leftline{ } 
which results in a bidiagonal matrix with main diagonal
\begin{displaymath}
\left( c_1 \ , \ c_2 \ , \ \ldots \ , \ c_{n-1} \ , \ k_n c_n \right)
\end{displaymath}
and lower first diagonal
\begin{displaymath}
\left( a_1 g_2 \ , \ \frac{g_3 k_2 f_2}{g_2} \ , \ \ldots \ , \ \frac{g_{n-1} k_{n-2} f_{n-2}}
                          {g_{n-2}} \ , \ \frac{k_n k_{n-1} f_{n-1}}{g_{n-1}} \right).
\end{displaymath} \\
\leftline{ }

Operation 3. $\textrm{row} \ 2 - \frac{a_1 g_2}{c_1} \times \textrm{row} \ 1,$ 

   $\textrm{~~~~~~~~~~~~~~~~~~row} \ i - \frac{g_i k_{i-1} f_{i-1}}{g_{i-1} c_{i-1}} \times \textrm{row} \ (i-1),
            \ \      i=3,4,\ldots,n-1, \ \ \ \ \textrm{and}$

   $\textrm{~~~~~~~~~~~~~~~~~~row} \ n - \frac{k_n k_{n-1} f_{n-1}}{g_{n-1} c_{n-1}} \times \textrm{row} \ (n-1),$ \\
\leftline{ }
which results in the diagonal matrix 
\begin{displaymath}
\left\lceil c_1 \ \ \ c_2 \ \ \ \ldots \ \ \ c_{n-1} \ \ \ k_n c_n \right\rfloor .
\end{displaymath} \\
\leftline{ }

Operation 4. $\frac{1}{c_i} \times \textrm{row} \ i, \ \ i=1,2,\ldots,n-1, \ \ \ \ \textrm{and}$

   $\textrm{~~~~~~~~~~~~~~~~~~} \frac{1}{k_n c_n} \times \textrm{row} \ n$ \\ 
\leftline{ }
which gives the identity matrix. \\
\leftline{ }

Operations 1--4 transform the identity matrix to the following forms, respectively. \\
\leftline{ }

Form 1. The bidiagonal matrix with main diagonal
\begin{displaymath}
\left( 1 \ , \ 1 \ , \ \ldots \ , \ 1 \ , \ 1 \right)
\end{displaymath}
and upper first diagonal
\begin{displaymath}
\left( -1 \ , \ -1 \ , \ \ldots \ , \ -1 \ , \ -1 \right).
\end{displaymath}

Form 2. The tridiagonal matrix consisting of the main diagonal
\begin{displaymath}
\left( 1 \ , \ 1 \ , \ 1 + \frac{g_3}{g_2} \ , \ \ldots \ , \ 1 + \frac{g_{n-1}}{g_{n-2}} \ , \
       1 + \frac{k_n}{g_{n-1}} \right),
\end{displaymath}
the upper first diagonal
\begin{displaymath}
\left( -1 \ , \ -1 \ , \ \ldots \ , \ -1 \ , \ -1 \right)
\end{displaymath}
and the lower first diagonal
\begin{displaymath}
\left( 0 \ , \ -\frac{g_3}{g_2} \ , \ \ldots \ , \ -\frac{g_{n-1}}{g_{n-2}} \ , \
       -\frac{k_n}{g_{n-1}} \right).
\end{displaymath}

Form 3. The lower Hessenberg matrix
\begin{displaymath}
\left[
\begin{array}{ccccc}
       1 & -1 & \ldots & 0 & 0                                                                      \\
       -\frac{a_1 g_2}{c_0 c_1} & \frac{k_1 b_1 - k_3 a_1}{c_1} & \ldots & 0 & 0                    \\
       \frac{a_1 g_3 k_2 f_2}{c_0 c_1 c_2} & -\frac{d_1 g_3}{c_1 c_2} & \ldots & 0 & 0              \\
       \ldots & & & &                                                                               \\
       s \frac{a_1 g_{n-1} k_2 f_2 \ldots k_{n-2} f_{n-2}}{c_0 c_1 \ldots c_{n-2}} &
       s \frac{d_1 g_{n-1} k_3 f_3 \ldots k_{n-2} f_{n-2}}{c_1 \ldots c_{n-2}}     &
       \ldots                                                                      &
       \frac{k_{n-2} b_{n-2} - k_n a_{n-2}}{c_{n-2}}                               & 
       -1                                                                                           \\
       \ \ s \frac{a_1 g_n k_n k_2 f_2 \ldots k_{n-1} f_{n-1}}{c_0 c_1 c_2 \ldots c_{n-1}}    \ \ &
       \ \ s \frac{d_1 g_n k_n k_3 f_3 \ldots k_{n-1} f_{n-1}}{c_1 c_2 \ldots c_{n-1}}        \ \ &
       \ \ \ldots                                                                             \ \ &
       \ \ -\frac{d_{n-2} g_n k_n}{c_{n-2} c_{n-1}} & \frac{k_{n-1} b_{n-1}}{c_{n-1}}         \ \ 
\end{array}
\right],
\end{displaymath}
where the symbol $s$ stands for $(-1)^{i+j}$. \\
\leftline{ }

Form 4. The inverse matrix given by the formulae (6). \\
\leftline{ } 

\subsection{The Determinant}
The determinant of $A_2$ has the form 
\begin{equation}
\textrm{det}(A_2) = k_n b_n \left( k_1 b_1 - k_2 a_1 \right) \left( k_2 b_2 - k_3 a_2 \right)
                    \ldots \left( k_{n-1} b_{n-1} - k_n a_{n-1} \right),
\end{equation}
which shows in turn that the matrix $A_2$ is singular if $k_n = 0$ or, adopting the conventions (6), $c_i = 0$ for some $i \in \left\{ 1,2,\ldots,n \right\}$. 

\section{Numerical Complexity}
The relations (3) and (8) lead to recurrence formulae, by which the inverses $A_1^{-1}$ and $A_2^{-1}$, respectively, are computed in $O(n^2)$ multiplications/divisions and $O(n)$ additions/substractions. In fact, the recursive algorithm
\begin{equation*}
\alpha_{i,i+1} = - 1 / c_i, \ \ \ i=1,2,\ldots,n-1,
\end{equation*}
\begin{equation*}
\alpha_{ii} = - \alpha_{i,i+1} + \frac{b_{i-1} g_i}{c_{i-1} c_i}, \ \ \ 
              i=2,3,\ldots,n-1, \ \ \ \alpha_{11}=\frac{k_2}{k_1 c_1}, \ \ \ 
              \alpha_{nn} = \frac{b_{n-1}}{c_{n-1} c_n},
\end{equation*}
\begin{equation*}
\alpha_{i,i-1} = - \frac{d_{i-2} g_i}{c_{i-2} c_{i-1} c_i}, \ \ \ i=2,3,\ldots,n,
\end{equation*}
\begin{equation*}
\alpha_{i,i-s-1} = - \ \frac{d_{i-s-2} k_{i-s} f_{i-s}}
                                 {d_{i-s-1} c_{i-s-2}} 
                     \ \alpha_{i,i-s}, \ \ \ i=3,4,\ldots,n, \ \ \ s=1,2,\ldots,i-2,
\end{equation*}
where the $c_i$, $d_i$, $f_i$, and $g_i$ are given by the relations (4), computes $A_1^{-1}$ in $5 n^2 / 2 + 5 n / 2 - 6$ mult/div (since the coefficients of $\alpha_{i,i-s}$ depends only on the second subscript) and $5 n - 9$ add/sub.

In terms of $j$, the above algorithm takes the following form
\begin{displaymath}
\alpha_{j-1,j} = - 1 / c_{j-1}, \ \ \ j=2,3,\ldots,n,
\end{displaymath}
\begin{displaymath}
\alpha_{jj} = - \alpha_{j,j+1} + \frac{b_{j-1} g_j}{c_{j-1} c_j}, \ \ \ 
              j=2,3,\ldots,n-1, \ \ \ \alpha_{11}=\frac{k_2}{k_1 c_1}, \ \ \ 
              \alpha_{nn} = \frac{b_{n-1}}{c_{n-1} c_n},
\end{displaymath}
\begin{displaymath}
\alpha_{j+1,j} = - \ \frac{d_{j-1} g_{j+1}}{c_{j-1} c_j c_{j+1}}, \ \ \ j=1,2,\ldots,n-1,
\end{displaymath}
\begin{displaymath}
\alpha_{j+s+1,j} = - \ \frac{g_{j+s+1} k_{j+s} f_{j+s}}
                                 {g_{j+s} c_{j+s+1}} 
                     \ \alpha_{j+s,j}, \ \ \ j=1,2,\ldots,n-2, \ \ \ s=1,2,\ldots,n-j-1.
\end{displaymath}
 

For the computation of $A_2^{-1}$ the above algorithms change only in the estimation of the diagonal elements, for which we have 
\begin{displaymath}
\alpha_{ii} = - \alpha_{i,i+1} + \frac{a_{i-1} g_i}{c_{i-1} c_i}, \ \ \ i=2,3,\ldots,n-1, \ \ \
                \alpha_{11} = - \alpha_{12}, \ \ \ \alpha_{nn} = \frac{k_{n-1} b_{n-1}}{k_n c_{n-1} c_n},
\end{displaymath}
where the $c_i$, $d_i$, $f_i$, and $g_i$ are given by the relations (9). Therefore, considering the relations (4) and (9), it is clear that the number of mult/div and add/sub in computing $A_2^{-1}$ is the same with that of $A_1^{-1}$.

\begin{thebibliography}{Valvi(1977)}

\bibitem[Carayannis, Kalouptsidis, \& Manolakis(1982)]{ckm82} Carayannis, G., Kalouptsidis, N., \& Manolakis, D. G.:
Fast recursive algorithms for a class of linear equations.
IEEE Trans. Acoust. Speech Sig. Proc. {\bfseries 30} (1982) 227--239

\bibitem[Gover \& Barnett(1986)]{gba86} Gover, M. J. C., \& Barnett, S.:
Brownian matrices: properties and extensions.
Int. J. Systems Sci. {\bfseries 17} (1986) 381--386

\bibitem[Herbold(1969)]{her69} Herbold, R. J.: 
A generalization of a class of test matrices.
Math. Comp.  {\bfseries 23} (1969) 823--826

\bibitem[Picinbono(1983)]{pic83} Picinbono, B.:
Fast algorithms for Brownian matrices.
IEEE Trans. Acoust. Speech Sig. Proc. {\bfseries 31} (1983) 512--514

\bibitem[Valvi(1977)]{val77} Valvi, F. N.:
Explicit presentation of the inverses of some types of matrices.
J. Inst. Maths. Applics. {\bfseries 19} (1977) 107--117 

\end{thebibliography} 
\end{document}




math0208075.extracted_bib
\begin{thebibliography}{Valvi(1977)}

\bibitem[Carayannis, Kalouptsidis, \& Manolakis(1982)]{ckm82} Carayannis, G., Kalouptsidis, N., \& Manolakis, D. G.:
Fast recursive algorithms for a class of linear equations.
IEEE Trans. Acoust. Speech Sig. Proc. {\bfseries 30} (1982) 227--239

\bibitem[Gover \& Barnett(1986)]{gba86} Gover, M. J. C., \& Barnett, S.:
Brownian matrices: properties and extensions.
Int. J. Systems Sci. {\bfseries 17} (1986) 381--386

\bibitem[Herbold(1969)]{her69} Herbold, R. J.: 
A generalization of a class of test matrices.
Math. Comp.  {\bfseries 23} (1969) 823--826

\bibitem[Picinbono(1983)]{pic83} Picinbono, B.:
Fast algorithms for Brownian matrices.
IEEE Trans. Acoust. Speech Sig. Proc. {\bfseries 31} (1983) 512--514

\bibitem[Valvi(1977)]{val77} Valvi, F. N.:
Explicit presentation of the inverses of some types of matrices.
J. Inst. Maths. Applics. {\bfseries 19} (1977) 107--117 

\end{thebibliography}