Métodos numéricos para matrices signo-regulares

XX Congreso de Ecuaciones Diferenciales y Aplicaciones X Congreso de Matem´ atica Aplicada Sevilla, 24-28 septiembre 2007 (pp. 1–??) M´etodos num´ericos para matrices signo-regulares V. Cort´ es, J. M. Pe˜ na Dpto. de Matem´atica Aplicada, Universidad de Zaragoza, E-50009 Zaragoza. E-mails: [email protected], [email protected]. Palabras clave: Matrices signo-regulares, eliminaci´on de Neville, estrategias de pivotaje Resumen Una matriz de orden nes signo-regular si para cada k(1 ≤k≤n) todos los menores de orden ktiene el mismo signo no estricto. Presentamos algunos avances recientes sobre el estudio de las matrices signo-regulares y sobre m´etodos num´ericos adaptados a las mismas. 1. Introducci´on Una matriz se llama signo-regular (SR) si para cada ktodos sus menores de orden k tienen el mismo signo o son nulos. Ese signo com´un puede ser distinto para cada k, pero si todos son no negativos las matrices se llaman totalmente no negativas. El inter´es de las matrices no singulares signo-regulares en muchas aplicaciones proviene de su caracterizaci´on como aplicaciones lineales que disminuyen la variaci´on de signo en las componentes consecutivas del vector. Con objeto de aclarar esta afirmaci´on, vamos a introducir algunas notaciones b´asicas. Para cualquier vector λ= (λ0, . . . , λn)∈Rn+1, denotaremos por V−(λ) al n´umero m´ınimo de cambios de signo en las componentes consecutivas de λy V+(λ) al n´umero m´aximo de cambios de signo en las componentes consecutivas de λ. Es decir, V−(λ) := m´ın ©k|existe 0 ≤i0< . . . < ik≤n, tal que (−1)jλij≥0 para todo j∈ {0, . . . , k}´o (−1)jλij≤0 para todo j∈ {0, . . . , k}ª, V+(λ) := m´ax ©k|existe 0 ≤i0< . . . < ik≤n, tal que (−1)jλij≥0 para todo j∈ {0, . . . , k}´o (−1)jλij≤0 para todo j∈ {0, . . . , k}ª. Claramente, si λtiene todas sus componentes no nulas entonces V−(λ) = V+(λ). El siguiente resultado se conoce como la propiedad de disminuci´on de la variaci´on de las matrices signo-regulares y por ´el las matrices no singulares signo-regulares tienen tanta importancia en las aplicaciones. 1 V. Cort´es, J. M. Pe˜na Teorema 1. (cf. [1], Theorem 5.6) Sea Auna matriz real no singular n×n. Entonces las siguientes condiciones son equivalentes: (i) Aes signo-regular. (ii) V+(Ax)≤V+(x)para todo x∈Rn. (iii) V−(Ax)≤V+(x)para todo x∈Rn. (iv) V−(Ax)≤V−(x)para todo x∈Rn. La teor´ıa de las transformaciones lineales que cumplen la propiedad de disminuci´on de la variaci´on tuvo su origen en Schoenberg [15]. Muchas aplicaciones de estas transformaciones se pueden encontrar en [9]. Para aplicaciones estad´ısticas de las matrices SR se puede consultar [2], y [11] para aplicaciones en dise˜no geom´etrico asistido por ordenador. Otras propiedades de las matrices SR se pueden ver en [13] y [12]. La eliminaci´on de Neville consiste en producir ceros en una matriz mediante la substracci´on a una fila dada de un m´ultiplo adecuado de su fila anterior hasta obtener una matriz triangular superior, y en el caso de las matrices no singulares totalmente no negativas se puede aplicar sin cambios de filas (v´ease [5]). Sin embargo, esto no ocurre para las matrices signo-regulares no singulares, como muestra la siguiente matriz: A=µ0 1 1 1¶. Por tanto, el uso de una estrategia de pivotaje es necesaria. La eliminaci´on de Neville se ha mostrado muy ´util en el tratamiento de matrices totalmente no negativas (v´ease [5]), que forman una subclase de matrices signo-regulares. En [3] se introduce una estrategia de pivotaje para la eliminaci´on de Neville de matrices signo-regulares. Aqu´ı se presentan aplicaciones y ventajas de dicha estrategia, que auguran que jugar´a un papel clave en los m´etodos num´ericos adaptados a las matrices signo-regulares, como ya sucedi´o con la eliminaci´on de Neville con respecto a las matrices totalmente no negativas. La estructura de este trabajo es la siguiente. En la secci´on 2 introducimos las notaciones b´asicas junto con la eliminaci´on de Neville. En la secci´on 3 introducimos la estrategia de pivotaje dos-determinantal para la eliminaci´on de Neville y recordamos alguna de sus propiedades m´as notables. En la secci´on 4 analizamos factorizaciones matriciales asociadas a esta estrategia de pivotaje. Finalmente, en la secci´on 5 relacionamos la estrategia dosdeterminantal con las estrategias de pivotaje parcial escalado. 2. Notaciones b´asicas. Dados k, n ∈N,k≤n,Qk,n representa el conjunto de todas las sucesiones estrictamente crecientes de kn´umeros naturales menores o iguales a m: α= (αi)1≤i≤k∈Qk,n,(1 ≤)α1< α2< . . . < αk(≤n). Para α= (α1, α2, . . . , αk), β = (β1, β2, . . . , βk)∈Qk,n yAuna matriz real n×n, denotaremos por A[α|β] a la submatriz k×kde Aque contiene las filas α1, α2, . . . , αky las 2 M´etodos num´ericos para matrices signo-regulares columnas β1, β2, . . . , βk. Si α=β, la submatriz principal A[α|α] de Ase denota por simplicidad como A[α]. Q0 k,n denotar´a el conjunto de las sucesiones estrictamente crecientes de kn´umeros naturales consecutivos menores o iguales a n. Para una matriz no singular Ade orden n, la eliminaci´on de Neville con una estrategia de pivotaje consiste en n−1 pasos sucesivos que dan lugar a la siguiente sucesi´on de matrices: A=A(1) →˜ A(1) →A(2) →˜ A(2) → · · · → A(n)=U, (1) donde Ues una matriz triangular superior. Para cada t, 1 ≤t≤n, las matrices A(t)= (a(t) ij )1≤i,j≤ny˜ A(t)= (˜a(t) ij )1≤i,j≤ntienen ceros por debajo de su diagonal principal en las primeras t−1 columnas, y adem´as se tiene ˜a(t) it = 0, i ≥t⇒˜a(t) ht = 0 ∀h≥i. (2) Partiendo de la matriz A(t)se obtiene la matriz ˜ A(t)reordenando las filas y/o columnas t, . . . , n conforme a la estrategia de pivotaje y cumpliendo (2). Para obtener A(t+1) hacemos ceros en la columna t-´esima de ˜ A(t)por debajo de la diagonal principal substrayendo un m´ultiplo de la fila i-´esima a la fila (i+ 1)-´esima para i=n−1, n −2, . . . , t, siguiendo la siguiente f´ormula. Para cualquier columna j= 1, . . . , n, a(t+1) ij :=      ˜a(t) ij ,si i≤t, ˜a(t) ij −(˜a(t) it /˜a(t) i−1,t)˜a(t) i−1,j,si i≥t+ 1 y ˜a(t) i−1,t 6= 0, ˜a(t) ij ,si i≥t+ 1 y ˜a(t) i−1,t = 0. (3) Observamos que en el tercer caso, ˜a(t) i−1,t = 0 implica ˜a(t) it = 0 por (2). Cuando el proceso no necesita de cambios de filas, entonces A(t)=˜ A(t)para todo t. Por ejemplo, en el caso de las matrices totalmente no negativas no singulares se puede aplicar la eliminaci´on de Neville sin cambios de filas ni de columnas (ver Corolario 5.5 de [7]). El elemento pij = ˜a(j) ij ,1≤j≤i≤n, (4) se llama pivote (i, j) de la eliminaci´on de Neville de Ay el n´umero mij =(˜a(j) ij /˜a(j) i−1,j(= pij/pi−1,j),si ˜a(j) i−1,j 6= 0, 0,si ˜a(j) i−1,j = 0 ³⇒˜a(j) ij = 0´,(5) para 1 ≤j≤n, j < i ≤n, el multiplicador (i, j) de la eliminaci´on de Neville de A. Observamos que mij = 0 si y s´olo si pij = 0 y que, por (2), mij = 0 ⇒mhj = 0, h =i+ 1, . . . , n. (6) Por signatura entendemos cualquier sucesi´on (infinita) real ε= (εi) con |εi|= 1, i= 1,2,... . Dado k≤m´ın{m, n}, una matriz m×n A es signo-regular de orden k con signatura εsi, para cada j= 1, . . . , k, todos los menores de orden jde la matriz Atienen el mismo signo no estricto que coincide con εj, y se denota por SRk. Si la matriz Aes SRk para todo k≤m´ın{m, n}, entonces se dice que la matriz es signo-regular y se denota por SR. 3 V. Cort´es, J. M. Pe˜na 3. La estrategia de pivotaje dos-determinantal para matrices signo-regulares Como hemos se˜nalado en la introudcci´on, es necesario asociar a la eliminaci´on de Neville una estrategia de pivotaje cuando se trabaja con matrices SR. En [3], se propone una estrategia de pivotaje por filas asociada a la eliminaci´on de Neville para las matrices SR no singulares. Esta estrategia recibe el nombre de pivotaje dos-determinantal, debido al papel especial que tienen algunos determinantes de orden 2 de las matrices que aparecen a lo largo del proceso de eliminaci´on de Neville. En general, para un paso t(1 ≤t≤n−1), una estrategia de pivotaje por filas en la eliminaci´on de Neville debe elegir una reordenaci´on de las filas de la matriz A(t)[t, . . . , n] dando lugar a una matriz nueva ˜ A(t)[t, . . . , n] cumpliendo (2). Sea Auna matriz n×nno singular signo-regular. Para t= 1, . . . , n −1, denotamos por Pt= (δn−t+2−i,j)1≤i,j≤n−t+1 a la matriz (n−t+ 1) ×(n−t+ 1) que es reversa de la matriz identidad, es decir, Pts´olo tiene unos en la diagonal secundaria y ceros en los dem´as lugares. El criterio de la estrategia de pivotaje dos-determinantal para obtener ˜ A(t)[t, . . . , n] mediante una reordenaci´on de las filas de A(t)[t, . . . , n] es el siguiente: - Si a(t) tt = 0, entonces revertimos el orden de las filas desde thasta n, es decir, ˜ A(t)[t, . . . , n] := Pt·A(t)[t, . . . , n]. - Si a(t) nt = 0, entonces no hacemos cambios de filas, es decir, ˜ A(t):= A(t). - Si a(t) tt 6= 0 y a(t) nt 6= 0, entonces calculamos el determinante d1:= det Ãa(t) tt a(t) t,t+1 a(t) t+1,t a(t) t+1,t+1!. - Si d1>0, entonces ˜ A(t):= A(t). - Si d1<0, entonces ˜ A(t)[t, . . . , n] := Pt·A(t)[t, . . . , n]. - Si d1= 0, calculamos el determinante d2:= det Ãa(t) n−1,t a(t) n−1,t+1 a(t) nt a(t) n,t+1 !. Si d2>0, entonces ˜ A(t):= A(t). Si d2<0, entonces ˜ A(t)[t, . . . , n] := Pt·A(t)[t, . . . , n]. Observamos que para aplicar la estrategia de pivotaje dos-determinantal en un paso t de la eliminaci´on de Neville son necesarias las siguientes condiciones: al menos uno de los elementos a(t) tt ´o a(t) nt debe de ser distinto de cero y si ambos son cero, entonces al menos uno de los menores d1´o d2debe de ser distinto de cero. En los lemas 3.2 y 3.3. de [3] se demuestra que esto ocurre si A(t)[t, . . . , n] es una matriz no singular signo-regular de orden 3 (SR3). Esta ´ultima condici´on se obtiene del Teorema 3.4 de [3] siempre que Asea una matriz no singular SR y se use el pivotaje dos-determinantal. El coste computacional de la eliminaci´on de Neville sin cambios de filas de una matriz n×ncoincide con el coste de la eliminaci´on de Gauss sin cambios de filas. Por tanto, 4 M´etodos num´ericos para matrices signo-regulares tiene un coste de O(n3) operaciones elementales. Usando la estrategia de pivotaje dosdeterminantal este coste se incrementa a lo sumo en 2n−2 substracciones y 4n−4 multiplicaciones. Por tanto, esta estrategia conlleva un coste computacional inferior al del pivotaje parcial. El siguiente resultado, demostrado en [3], muestra que la signo-regularidad es una propiedad que se hereda por todas las matrices A(t)[t, . . . , n] que aparecen al aplicar la eliminaci´on de Neville con pivotaje dos-determinantal. Teorema 2. (cf. [3], Theorem 3.4) Sea A= (aij)1≤i,j≤nuna matriz no singular signoregular a la que aplicamos la eliminaci´on de Neville con pivotaje dos-determinantal. Entonces, para k∈ {1, . . . , n}, todas las matrices A(k)[k, . . . , n]son signo-regulares y adem´as, ε1(A(k)) = ε1(A). Nota 1. Teniendo en cuenta la demostraci´on del teorema anterior (v´ease Teorema 3.4 de [3]), se tiene que para matrices no singulares totalmente no negativas, el pivotaje dosdeterminantal no produce cambios de filas. 4. Factorizaciones matriciales asociadas a la eliminaci´on de Neville con pivotaje dos-determinanatal A lo largo de esta secci´on, analizaremos en detalle el caso de una matriz SR no singular Aa la que aplicamos la eliminaci´on de Neville con el pivotaje dos-determinantal. Vamos a ver c´omo este proceso de eliminaci´on se puede describir mediante matrices elementales y matrices de permutaci´on. Con este fin y siguiendo [8], denotamos por Ei(α) (2 ≤i≤n) a la matriz triangular inferior bidiagonal cuyo elemento (r, s),1≤r, s ≤nest´a dado por    1 si r=s αsi (r, s) = (i, i −1) 0 en otro caso, es decir, Ei(α) :=             1 1 ... 1 α1 ... 1             .(7) Observamos que E−1 i(α) = Ei(−α).(8) Teniendo en cuenta la definici´on hecha en (??) para la matriz de permutaci´on Ptde orden n−t+ 1 (1 ≤t≤n−1), podemos definir ˜ Ptcomo la matriz de orden ndada por ˜ Pt=µIt−10 0Pt¶, 5 V. Cort´es, J. M. Pe˜na donde It−1es la matriz identidad de orden t−1. Supongamos que, para una matriz SR no singular Ade signo ε1, la eliminaci´on de Neville con pivotaje dos-determinantal tiene asociadas r, con r≤n−1, permutaciones en los pasos i1,...ir(1 ≤i1< i2< . . . < ir≤n−1). De este modo, podemos definir la siguiente matriz: ˆ Pi:= ½˜ Pisi i∈ {i1, . . . , ir}, Inen otro caso. Entonces la eliminaci´on de Neville con pivotaje dos-determinantal de Ase puede escribir como ˆ Pn−1En(−mn,n−1)· · · (E3(−m32)· · · En(−mn2)) ˆ P2 ·(E2(−m21)· · · En−1(−mn−1,1)En(−mn1)) ˆ P1A=U, (9) donde Ues una matriz no singular triangular superior, y los mij’s son los multiplicadores (5) que cumplen (6). Observamos que, por el Teorema 2, Ues una matriz de signo constante ε1. Teniendo en cuenta (8), por (9) conseguimos la siguiente factorizaci´on de A A=ˆ P1(En(mn1)En−1(mn−1,1)· · · E2(m21)) ·ˆ P2(En(mn2)· · · E3(m32)) · · · ˆ Pn−1En(mn,n−1)U. (10) Notemos que los elementos diagonales uii de Uson los pivotes pii dados por (4). Como, por el Teorema 2 A(t)[t, . . . , n] es SR para cada t∈ {1, . . . , n},Aes SR, por (5), se sigue que los multiplicadores mij son todos no negativos. Ahora, si denotamos por Li:= En(mni)· · · Ei+1(mi+1,i),(11) entonces, para todo i= 1, . . . , n −1, la matriz Lies triangular inferior, y adem´as, por el Teorema 3.1 de [1], es totalmente no negativa por ser producto de matrices totalmente no negativas. Finalmente teniendo en cuenta (11), podemos escribir (10) como A=ˆ P1L1ˆ P2L2· · · ˆ Pn−1Ln−1U. (12) Por tanto, por (12), dada una matriz n×n A no singular SR, su eliminaci´on de Neville con pivotaje dos-determinantal nos permite factorizar la matriz Acomo producto de n−1 matrices triangulares totalmente no negativas, n−1 matrices de permutaci´on (quiz´as algunas de ellas la matriz identidad) y una matriz triangular superior Ucon el mismo signo de A. La factorizaci´on dada en (12) se puede utilizar para llevar a cabo un an´alisis de error de la eliminaci´on de Neville con la estrategia dos-determinantal cuando se aplica a la resoluci´on de sistemas de ecuaciones lineales. Es bien conocido en el contexto del an´alisis de error “backward” que una factorizaci´on (como (12)) de una matriz con signo constante en la que todas las matrices triangulares inferiores son no negativas y la triangular superior tiene signo constante conduce a peque˜nos errores “backward”. Adem´as la factorizaci´on (12) tiene una potencial aplicaci´on al c´alculo de valores propios con alta precisi´on relativa, como ya se ha visto en las factorizaciones particulares que aparecen en los casos de matrices totalmente no negativas o reversas de totalmente no negativas (v´ease [10]). 6 M´etodos num´ericos para matrices signo-regulares 5. Pivotaje parcial escalado en la eliminaci´on de Neville El estudio de estrategias de pivotaje alternativas a las cl´asicas del pivotaje parcial y del pivotaje completo constituye una activa l´ınea de investigaci´on actual (v´ease, por ejemplo, [4] y sus referencias). En esta secci´on consideramos las estrategias de pivotaje parcial escalado (SPP) asociadas a la eliminaci´on de Neville. Para cada paso t, 1 ≤t≤n−1, de la eliminaci´on de Neville de una matriz no singular Ade orden n, hemos visto que tenemos que reordenar las filas t, . . . , n de la matriz A(t)(v´ease (1)) siguiendo una estrategia de pivotaje por filas con objeto de encontrar la matriz ˜ A(t)cumpliendo (2). An´alogamente al caso de la eliminaci´on de Gauss, con el fin de conservar los valores absolutos de los multiplicadores ˜a(t) it /˜a(t) i−1,t menores o iguales a 1, podemos definir el pivotaje parcial en la eliminaci´on de Neville como el proceso que reordena las filas de la matriz A(t)para obtener ˜ A(t)donde |˜a(t) tt | ≥ |˜a(t) t+1,t| ≥ . . . ≥ |˜a(t) nt | Para mejorar esta estrategia con un escalado adecuado, siguiendo [6] podemos definir el pivotaje parcial escalado (SPP) para la norma vectorial k · k en la eliminaci´on de Neville. Denotemos por r(t) ia la fila i-´esima (i=t, t + 1, . . . , n yt= 1, . . . , n) de la matriz A(t)[1,2, . . . , n|t, t + 1, . . . , n]. Para cada t= 1, . . . , n −1, si se tiene |a(t) i1,t| kr(t) i1k≥|a(t) i2,t| kr(t) i2k≥. . . ≥|a(t) in−t+1,t| kr(t) in−t+1 k para una permutaci´on (i1, i2, . . . , in−t+1) de (t, t + 1, . . . , n), entonces la estrategia SPP para la norma vectorial k · k en la eliminaci´on de Neville reemplaza la fila t-´esima de A(t) por la fila i1-´esima, la fila (t+ 1)-´esima por la i2-´esima, y as´ı se contin´ua sucesivamente. Trabajaremos, en particular, con estrategias de SPP asociadas a normas vectoriales mon´otonas. Como ejemplo de normas vectoriales mon´otonas, consideraremos las normas vectoriales k·k∞,k · k2yk · k1. En el caso particular de la norma k·k2, la estrategia de SPP asociada (para la eliminaci´on de Gauss o de Neville) se llama pivotaje parcial escalado eucl´ıdeo (ESPP). Esta estrategia, tanto para Gauss como para Neville, da lugar a un sistema triangular donde el hiperplano de Rnasociado a su i-´esima ecuaci´on (i= 1,2, . . . , n) est´a bien orientado con respecto al eje xi. Esto significa que, en el paso i, seleccionamos como hiperplano i-´esimo el que es m´as ortogonal al eje xi(observamos que esta estrategia est´a basada en los cosenos directores). V´ease [6] y [14]. Concretamente, en el caso del ESPP para la eliminaci´on de Neville, las filas de ˜ A(i)[i, . . . , n] est´an todas ordenadas de tal forma que el hiperplano iasociado a la fila ide ˜ A(i)es m´as ortogonal al eje xique el hiperplano (i+ 1), que a su vez es m´as ortogonal al eje xique el hiperplano (i+ 2), y as´ı, sucesivamente. El siguiente resultado, cuya demostraci´on se recoge en [3], muestra que la estrategia de pivotaje dos-determinantal es una estrategia de pivotaje parcial escaldo para la eliminaci´on de Neville. Teorema 3. (cf. [3], Theorem 4.1) Sea A= (aij)1≤i,j≤nuna matriz no singular signoregular. La estrategia de pivotaje dos-determinantal para la eliminaci´on de Neville es una estrategia de pivotaje parcial escalado para cualquier norma vectorial mon´otona k · k. 7 V. Cort´es, J. M. Pe˜na Nota 2. El Teorema 3 (para la norma eucl´ıdea k · k2) y la interpretaci´on geom´etrica dada anteriormente para las estrategias de ESPP demuestran que los hiperplanos asociados a las ecuaciones de un sistema lineal Ax =b, con Amatriz signo-regular, est´an ordenados decrecientemente (resp., crecientemente) con respecto a su ortogonalidad con el eje x1, si ε2(A) = +1 (resp., ε2(A) = −1). En otras palabras, la primera permutaci´on de la estrategia de pivotaje dos-determinantal reordena los hiperplanos de tal modo que el primer hiperplano es m´as ortogonal al eje x1que el segundo hiperplano, que el segundo es m´as ortogonal al mismo eje que el tercer hiperplano, y as´ı, sucesivamente. Una interpretaci´on similar se establece con respecto al eje xiy a la elecci´on de las filas de A(i)[i, . . . , n] determinada por el pivotaje dos-determinantal. Adem´as, destacamos que la estrategia de ESPP tiene, en teor´ıa, un alto coste computacional; sin embargo en la pr´actica, podemos implementarla aplicando la estrategia del pivotaje dos-determinantal que es m´as econ´omica incluso que el pivotaje parcial. Agradecimientos Este trabajo est´a apoyado por el Spanish Research Grant MTM2006-03388 y por el Gobierno de Arag´on y el Fondo Social Europeo. Referencias [1] T. Ando, Totally Positive Matrices, Linear Algebra Appl. 90 (1987), 165–219. [2] L. D. Brown, I. M. Johnstone, K. B. MacGibbon, Variation Diminishing transformations: a direct approach to total positivity and its statistical applications, Journal of the American Statistical Association 76 (1981), 824–832. [3] V. Cort´es, J. M. Pe˜na, Sign regular matrices and Neville elimination, Linear Algebra Appl. 421 (2007), 53–62. [4] V. Cort´es, J. M. Pe˜na, Growth factor and expected growth factor of some pivoting strategies, J. Comput. Appl. Math. 202 (2007), 292–303. [5] M. Gasca, J. M. Pe˜na, Total positivity and Neville elimination, Linear Algebra Appl. 165 (1992), 25–44. [6] M. Gasca, J. M. Pe˜na, Scaled pivoting for Gaussian and Neville elimination for totally positive systems, Appl. Numer. Math. 13 (1993), 345–355. [7] M. Gasca, J. M. Pe˜na, Total positivity, QR factorization and Neville elimination, SIAM J. Matriz Anal. Appl. 14 (1993), 1132–1140. [8] M. Gasca, J. M. Pe˜na, On factorizations of totally positive matrices, Total Positivity and Its Applications, M. Gasca, C. A. Micchelli (eds.), Kluwer Academic Publishers, 1996, 109–130. [9] S. Karlin, Total Positivity, Stanford University Press, Stanford, 1968. [10] P. Koev, F. Dopico, Accurate eigenvalues of certain sign-regular matrices. Aparecer´a en Linear Algebra Appl. [11] J. M. Pe˜na (Ed.), Shape preserving representations in Computer-Aided Geometric Design, Nova Science Publishers, Commack (New York), 1999. [12] J. M. Pe˜na, Sign regular matrices of order two, Linear Multilinear Algebra 50 (2002), 91–97. [13] J. M. Pe˜na, On nonsingular sign regular matrices, Linear Algebra Appl. 359 (2003), 91–100. [14] G. Poole, L. Neal, A geometric analysis of Gaussian elimination I, Linear Algebra Appl. 149 (1991), 249–272. [15] I. J. Schoenberg, Uber Variationsverminderende lineare Transformationen, Math. Z. 32 (1930), 321– 328. 8