Hello.

I understand that the following phenomenon is known, but I can not find
a reference to it. Any such reference would be a great help.

The situation is as follows: Let A be an non singular n by n narrow
banded matrix. Partion inv(A) into a block matrix with blocksize p, 1
p << n. Then under very general circumstances, the (numerical) rank of
the blocks will decay rapidly as you move away from the main block
diagonal. By the numerical rank of a matrix I mean the number of
singular values larger than say 1e-6 times the largest singular value.

I observed this phenomenon for several banded matrices, including
matrices that were far from diagonally dominant.

I am especially interested in theorems that given bounds on the
numerical rank of the off diagonal blocks.

I don't think that's true in general, see e.g.
inv(eye(8,-diag(ones(7,1),-1))
in Scilab (Matlab) notation

If, on the other hand, the matrix arises by discretization of an
elliptic operator (e.g. Laplace) it is intimately connected with Green's
function of that operator.
The inverse matrix is a sort of discrete Green's function.
As far as I remember, you can get estimates by estimating that
Green's function.
Sorry, I don't have a reference to some estimate at hand.

Helmut Jarausch wrote:

I don't think that's true in general, see e.g.
inv(eye(8,-diag(ones(7,1),-1))
in Scilab (Matlab) notation

If, on the other hand, the matrix arises by discretization of an
elliptic operator (e.g. Laplace) it is intimately connected with
Green's function of that operator.
The inverse matrix is a sort of discrete Green's function.
As far as I remember, you can get estimates by estimating that
Green's function.
Sorry, I don't have a reference to some estimate at hand.


Thank you for replying.

I like your example, but is it a counterexample? If

A = diag(ones(1,n))-diag(ones(1,n-1),-1)

then A is narrow banded and inv(A) is a lower triangular matrix with
every entry below the main diagonal equal to 1, independent of the
dimension n of the matrix. If you partion inv(A) into a block matrix,
then all the diagonal blocks will have full rank, all the super
diagonal block will be zero blocks and have rank 0, and all the sub
diagonal blocks will have rank 1. These observations are independent of
the block size.

Is it the absolute size of the individual elements or the (numerical)
rank of various blocks, i.e. groups of elements, of inv(A) that is
estimated by studying the Greens function for the differential operator
which is itself discretized as matrix A?

For a non singular banded matrix A it can be shown that there exist
constants C > 0, 0 < l < 1 such that

|inv(A)(i,j)| < C l^(|i-j|)

i.e. that the elemenents decay exponentially when you move away from the
main diagonal and there are simple formulas for calculating these
constants which are given in

Demko, S., Moss, W. F., Smith, P. W. "Decay Rates for Inverses of Band
Matrice". Mathematics of Computation, Vol 43, No. 168, October 1986, pp.
491-499

The constants can be calculated in terms of the smallest and the largest
singular value and the bandwidth, if the condition number is small, if
the bandwidth is small and if the smallest singular value is not to
small, then you will see rapid decay.

Let A be the adjacency matrix of the linear chain
a(i=j-1) and a(i-1=j) = -1, 0 otherwise.
Than 2I -A have inverses and they full rank matrices.
kunzmilan


Thanks for replying.

kunzmilan wrote:
Let A be the adjacency matrix of the linear chain
a(i=j-1) and a(i-1=j) = -1, 0 otherwise.
Than 2I -A have inverses and they full rank matrices.
kunzmilan

Thanks for replying.

I do not believe that I understand you correctly!
I apologize for -1. it should be just 1 to use -A

0 1 0
1 0 1
0 1 0

If this is the case then 2I-A is the tridiagonal Toeplitz matrix with 2
on the main diagonal and -1 on the first super and sub diagonal, i.e for
m = 3:

2 -1 0
-1 2 -1
0 -1 2
Its inverse (multiplied by a factor) is
3 2 1
2 4 2
1 2 3
The diagonal elements are sums of arcs on walks to other vertices,

Hello.

I would like to thank everybody for their input.

I tripped over a very relevant reference today:

E. Asplund: Inverse of matrices {a_ij} which satisfy a_ij=0 for j>i+p,
Math. Scand 7. (1959) 57-60.

Briefly the main result is a follows:

If A is a non singular matrix with a_ij=0 for j>i+p then inv(A) is a
(p,p) Greens matrix: any sub block of inv(A) contained in the region
where j>i+p has rank at most p regardless of the size of the block.

An example: Let A be a non singular tridiagonal (p=1) matrix of size m =
1e6. Let B=inv(A). Then the block B(1:499999,500001:1000000) has rank at
most 1.

Similarly if A is a non singular banded matrix with bandwidth p then any
sub block of inv(A) which does not encroach upon the band will have
rank at most p.

I did a few experiments which indicate that the numerical rank can be
much smaller than p, i.e. the off diagonal blocks can be accurately
approximated with matrices of rank much smaller than p.

/Carl Christian.

This is a well-studied field in matrix analysis which is about
"semiseparable matrices" --- matrices, that, for example,
are inverses of tri-diagonal matrices have all off-diagonal blocks of
rank not higher that 1.
Useful reading on this topic:http://www.cs.kuleuven.ac.be/~raf/
homepage/publications/papers_html/history/ -- all included
It is worth to mention that probably the first result was obtained in
1937 in the paper
F.R. Gantmacher and M.G. Krein.
Sur les matrices oscillatoires et completement non negatives.
Compositio Mathematica, 4:445-476, 1937

Dear Ivan Oseledets.