L-matrix

Matrices playing a central role in the study of qualitative economics and first defined by P.A. Samuelson [a6]. A real $( m \times n )$-matrix $A$ is an $L$-matrix provided every matrix with the same sign pattern as $A$ has linearly independent rows. For example,

\begin{equation*} M = \left( \begin{array} { c c c } { 1 } & { - 1 } & { 0 } \\ { 1 } & { 1 } & { - 1 } \\ { 1 } & { 1 } & { 1 } \end{array} \right) , \quad N = \left( \begin{array} { c c c c } { 1 } & { 1 } & { 1 } & { - 1 } \\ { 1 } & { 1 } & { - 1 } & { 1 } \\ { 1 } & { - 1 } & { 1 } & { 1 } \end{array} \right) \end{equation*}

are $L$-matrices. A linear system of equations, $A x = b$, is called sign-solvable provided the signs of the entries in any solution can be determined knowing only the signs of the entries in $A$ and $b$. If the linear system $A x = b$ is sign-solvable, then $A ^ { T }$ is an $L$-matrix. General references for this area include [a1], [a3] and [a4].

The study of $L$-matrices has included characterizations of structural properties, classification of subclasses as well as interrelationships with other discrete structures. For example, two subclasses of $L$-matrices which arise are that of the barely $L$-matrices and the totally $L$-matrices.

An $( m \times n )$-matrix $A$ is a barely $L$-matrix provided that $A$ is an $L$-matrix but if any column of it is deleted, the resulting matrix is not an $L$-matrix.

An $( m \times n )$-matrix $A$ is a totally $L$-matrix provided that each $( m \times m )$-submatrix of $A$ is an $L$-matrix.

The two matrices $M$ and $N$ above are examples of barely $L$-matrices. The matrix $M$ is also a totally $L$-matrix but $N$ is not since its $( 3 \times 3 )$-submatrix made up of the first three columns is not an $L$-matrix. The matrix

\begin{equation*} T = \left( \begin{array} { c c c c } { 1 } & { 1 } & { 1 } & { 0 } \\ { 1 } & { - 1 } & { 0 } & { 1 } \end{array} \right) \end{equation*}

is a $( 2 \times 4 )$ totally $L$-matrix.

The property of being a barely $L$-matrix, or a totally $L$-matrix, imposes restrictions on the number of columns. If $A$ is an $( m \times n )$ barely $L$-matrix, then the number of columns is at most $2 ^ { m - 1 }$; further, if $A$ has only non-negative entries, then the number of columns is at most

\begin{equation*} \left( \begin{array} { c } { m } \\ { \lceil \frac { m + 1 } { 2 } \rceil } \end{array} \right). \end{equation*}

If $A$ is an $( m \times n )$ totally $L$-matrix, then the number of columns is at most $m + 2$. It has been shown that the set of all $m$ by $m + 2$ totally $L$-matrices can be obtained from the matrix $T$ above by performing certain extension operations on $T$ successively [a2].

An important subclass of the $L$-matrices for which there exist a great deal of literature is that of the square $L$-matrices, which are also called sign-non-singular matrices.

References

[a1]	L. Bassett, J. Maybee, J. Quirk, "Qualitative economics and the scope of the correspondence principle" Econometrica , 36 (1968) pp. 544–563
[a2]	R.A. Brualdi, K.L. Chavey, B.L. Shader, "Rectangular L-matrices" Linear Algebra Appl. , 196 (1994) pp. 37–61
[a3]	R.A. Brualdi, B.L. Shader, "Matrices of sign solvable systems" , Tracts in Math. , 116 , Cambridge Univ. Press (1995)
[a4]	V. Klee, R. Ladner, R. Manber, "Sign-solvability revisited" Linear Algebra Appl. , 59 (1984) pp. 131–157
[a5]	R. Manber, "Graph-theoretical approach to qualitative solvability of linear systems" Linear Algebra Appl. , 48 (1982) pp. 131–157
[a6]	P.A. Samuelson, "Foundations of economic analysis" , Economic Studies , 80 , Harvard Univ. Press (1947)