<<

. 10
( 83 .)



>>

¬ ·
˜
A=¬ ·
 
—¦

˜K
0 A —¦
I
with
—¦ —¦ —¦ —¦

˜K K ˜K K
A =A ; A =A :
—¦ —¦ —¦ —¦
I I I I
—¦ —¦
˜ ˜—¦ ˜
The submatrix S := A( K ) of A is called the Schur complement of A( K ) in A with respect to the
—¦
I I
—¦
e.s. and the column list K , and is also denoted by
—¦
I K
˜
S= A A :
—¦
I I
˜
—¦
When = as in (11) and K = {1; : : : ; k}, then S is the classical Schur complement, which can
also be written as
’1
—¦ —¦ —¦ —¦ —¦

˜K K K K K
A =A ’A A A :
—¦ —¦ —¦ —¦ —¦
I I I I I
42 M. Gasca, G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 37“50

—¦
When = N is the Neville (k; m)“e.s. (12) and K = {1; : : : ; k}, then the rows of the Schur
—¦
˜ ˜—¦
complement S = A( K ) are
I
’1
—¦ —¦ —¦ —¦ —¦

˜K K K K K
A =A ’A A A s=1; : : : ; m:
k +s k +s k +s s; : : : ; s + k ’ 1 s; : : : ; s + k ’ 1
Whereas, the Schur complement of a submatrix depends essentially on the elimination strategies used,
its determinant does not! There holds the following generalization of Schur™s classical determinantal
identity [21,22,44]:
—¦ —¦
I K I K
ÿ
det A = (’1) det A det A A
—¦ —¦
I I I I
—¦
for all e.s. ∈ E(k; m; I ), where ÿ is an integer depending only on and K .
Also, Sylvester™s classical determinantal identity [55,56] has a corresponding generalization, see
[18,21,22,43,44] for details. In the case of Gauss elimination we get Sylvester™s classical identity
[9,10,55,56]
t=1; :::; m m’1
1; : : : ; k; k + t 1; : : : ; k
det A = det A A :
1; : : : ; k; k + s 1; : : : ; k
s=1;:::;m

In the case of Neville elimination one has
t=1; :::; m m
1; : : : ; k; k +t 1; : : : ; k
det A = det A A :
s; : : : ; s + k ’ 1; s + k s; : : : ; s + k ’ 1
s=1;:::;m s=2

Another identity of Sylvester™s type has been derived in [3]. Also some applications to the E-algorithm
[5] are given there.
As we have seen, the technique of e.s. has led us in particular to general determinantal identities
of Sylvester™s type. It can also be used to extend determinantal identities in the sense of Muir [51],
see [47].


5. Application to quasilinear extrapolation problems

Suppose we are given elements f1 ; : : : ; fN of a linear space E and elements L1 ; : : : ; LN of its dual
E . Consider furthermore elements f =: fN +1 of E and L =: LN +1 of E — . Setting I = (1; : : : ; N + 1),


by A we denote the generalized Vandermonde matrix
I f1 ; : : : ; fN ; fN +1 j=1; :::; N +1
A=A =V := Li ; fj : (13)
I L1 ; : : : ; LN ; LN +1 i=1;:::;N +1


Assume now that k; m ∈ N; m6N + 1 ’ k and that
—¦
= ((Is ; Is ))s=1; :::; m (14)
m
is a (k ’ 1; m)“e.s. over s=1 Is ‚(1; : : : ; N ): Let G := (1; : : : ; k): If the submatrices
G
A are nonsingular for s = 1; : : : ; m; (15)
Is
M. Gasca, G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 37“50 43


then for s = 1; : : : ; m the interpolants
k
k k
ps (f) := cs; j (f) · fj ; (16)
j=1

satisfying the interpolation conditions
k
Li ; ps (f) = Li ; f for i ∈ Is
are well deÿned as well as
k k
s (f) := L; ps (f) :
Clearly, in case of general linear extrapolation the mapping
k
ps
k
E f ’ ps (f)
is a linear projection onto span{f1 ; : : : ; fN } and
k
cs; j
k
E f ’ cs; j (f)
k
is a linear functional. In case of quasilinear extrapolation we assume that, as a function of f ∈ E; ps
k
remains idempotent. Then, as a function of f ∈ E, in general the coe cients cs; j (f) are not linear.
k
We assume that, as functions of f ∈ span{f1 ; : : : ; fN }; cs; j (f) remain linear.
The task is
(i) to ÿnd conditions, such that p1 (f); N (f) are well deÿned, and
N
1
(ii) to ÿnd methods to compute these quantities from ps (f); k (f)(s = 1; : : : ; m), respectively.
k
s

When translated into pure terms of Linear Algebra these questions mean: Consider matrix (13) and
assume (15),
(i) under which conditions can we ensure that A( 1;:::;N ) is nonsingular?
1;:::;N
The coe cient problem reads:
(ii ) Suppose that we do know the solutions
k k
cs (f) = (cs; j (f))j=1; :::; k
of the linear systems
G N +1
k
A · cs (f) = A ; s = 1; : : : ; m:
Is Is
N N
How to get from these the solution c1 (f) = (c1; j (f))j=1; :::; N of
1; : : : ; N N +1
N
A · c1 (f) = A ?
1; : : : ; N 1; : : : ; N
The value problem reads:
(iii) Suppose that we do know the values
k k
s (f) = L; ps (f) ; s = 1; : : : ; m:
How to get from these the value N (f) = L; p1 (f) ?
N
1
A dual coe cient problem can be also considered interchanging the roles of the spaces E and E — .
These problems were considered and solved in [20,7,19,31,40 “ 42,45,48,50].
44 M. Gasca, G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 37“50


6. Applications to special classes of matrices

General elimination strategies, in particular the Neville e.s. and generalized Schur complements
have found other applications in matrix theory and related problems.
In [21,22,44] we have considered some classes Ln of real n — n-matrices A including the classes
(i) Cn of matrices satisfying det A( J ) ¿ 0 for all J ‚(1; : : : ; n); det A( K ) · det A( K ) ¿ 0 for all
J
J J
J; K ‚(1; : : : ; n) of the same cardinality, which was considered in [36];
(ii) of symmetric positive-deÿnite matrices;
(iii) of strictly totally positive matrices (STP), which are deÿned by the property that all square
submatrices have positive determinants [36];
(iv) of Minkowski matrices, deÿned by
j 1; : : : ; k
A ¡0 for all i = j; det A ¿0 for all 16k6n:
i 1; : : : ; k
In [21] we have proved that
˜
A ∈ Ln ’S ∈ Lm ;
˜
where m=n’k and S denotes the classical Schur complement of A( 1;:::;k ) in A. For STP matrices also
1;:::;k
generalized Schur complements with respect to the Neville e.s. are STP. Using the Neville e.s. in
[21,49] tests of algorithmic complexity O(N 4 ) for matrices being STP were derived for the ÿrst time.
Neville elimination, based on consecutivity, proved to be especially well suited for STP matrices,
because these matrices were characterized in [36] by the property of having all subdeterminants with
consecutive rows and columns positive.
Elimination by consecutive rows is not at all new in matrix theory. It has been used to prove
some properties of special classes of matrices, for example, totally positive (TP) matrices, which,
as it has already been said, are matrices with all subdeterminants nonnegative. However, motivated
by the above mentioned algorithm for testing STP matrices, Gasca and Pe˜ a [24] initiated an ex-
n
haustive study of Neville elimination in an algorithmic way, of the pivots and multipliers used in
the proccess to obtain new properties of totally positive matrices and to improve and simplify the
known characterizations of these matrices.
Totally positive matrices have interesting applications in many ÿelds, as, for example, vibrations of
mechanical systems, combinatorics, probability, spline functions, computer-aided geometric design,
etc., see [36,37]. For this reason, remarkable papers on total positivity due to specialists on these
ÿelds have appeared, see for example the ones collected in [29].
The important survey [2] presents a complete list of references on totally positive matrices before
1987. One of the main points in the recent study of this class of matrices has been that of charac-
terizing them in practical terms, by factorizations or by the nonnegativity of some minors (instead
of all of them, as claimed in the deÿnition).
In [24] for example, it was proved that a matrix is STP if and only if all subdeterminants with lists
of consecutive rows and consecutive columns, starting at least one of these lists by 1, are positive.
Necessarily, one of the lists must start with 1. Observe, that the new characterization considerably
decreases the number of subdeterminants to be checked, compared with the classical characterization,
due to Fekete and PÃ lya [17], which used all subdeterminants with consecutive rows and columns.
o
M. Gasca, G. Muhlbach / Journal of Computational and Applied Mathematics 122 (2000) 37“50 45


This result means that the set of all subdeterminants of a matrix A with consecutive rows and
columns, of the form
1; : : : ; j i; : : : ; i + j ’ 1
A ; A ;
i; : : : ; i + j ’ 1 1; : : : ; j
called in [24] column- and row-initial minors, play in total positivity a similar role to that of the
leading principal minors
1; : : : ; j
A
1; : : : ; j
in positive deÿniteness of symmetric real matrices. An algorithm based on Neville elimination was
given in [24] with a complexity O(N 3 ) for a matrix of order N , instead of the one with O(N 4 ) previ-
ously obtained in [21,49]. Other similar simpliÿcations were obtained in [24] for the characterization
of totally positive matrices (not strictly).
Concerning factorizations, in [26] Neville elimination was described in terms of a product by
bidiagonal unit-diagonal matrices. Some of the most well-known characterizations of TP and STP
matrices are related to their LU factorization. Cryer [14,15], in the 1970s, extended to TP matrices
what was previously known for STP matrices, thus obtaining the following result.
A square matrix A is TP (resp. STP) i it has an LU factorization such that L and U are TP
( STP).
Here, as usual, L (resp. U ) denotes a lower (upper) triangular matrix and STP means triangular
nonnegative matrices with all the nontrivial subdeterminants of any order strictly positive.
Also Cryer pointed out that the matrix A is STP i it can be written in the form
N M
A= Lr Us
r=1 s=1

where each Lr (resp. Us ) is a lower (upper) STP matrix. Observe that this result does not mention
the relation of N or M with the order n of the matrix A.
The matricial description of Neville elimination obtained in [26] produced in the same paper the
following result.
Let A be a nonsingular matrix of order n. Then A is STP i it can be expressed in the form:
A = Fn’1 · · · F1 DG1 · · · Gn’1 ;
where, for each i=1; 2; : : : ; n’1; Fi is a bidiagonal, lower triangular, unit diagonal matrix, with zeros
in positions (2; 1); : : : ; (i; i ’ 1) and positive entries in (i + 1; i); : : : ; (n; n ’ 1); Gi has the transposed
form of Fi and D is a diagonal matrix with positive diagonal.
Similar results were obtained in [26] for TP matrices. In that paper all these new characterizations
were collected in three classes: characterizations in terms of determinants, in terms of algorithms
and in terms of factorizations.

<<

. 10
( 83 .)



>>