Namespaces
Variants
Actions

Difference between revisions of "L-matrix"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 58 formulas out of 58 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
Matrices playing a central role in the study of qualitative economics and first defined by P.A. Samuelson [[#References|[a6]]]. A real <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200102.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200103.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200104.png" />-matrix provided every matrix with the same sign pattern as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200105.png" /> has linearly independent rows. For example,
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200106.png" /></td> </tr></table>
+
Out of 58 formulas, 58 were replaced by TEX code.-->
  
are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200107.png" />-matrices. A linear system of equations, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200108.png" />, is called sign-solvable provided the signs of the entries in any solution can be determined knowing only the signs of the entries in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l1200109.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001010.png" />. If the linear system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001011.png" /> is sign-solvable, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001012.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001013.png" />-matrix. General references for this area include [[#References|[a1]]], [[#References|[a3]]] and [[#References|[a4]]].
+
{{TEX|semi-auto}}{{TEX|done}}
 +
Matrices playing a central role in the study of qualitative economics and first defined by P.A. Samuelson [[#References|[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,
  
The study of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001014.png" />-matrices has included characterizations of structural properties, classification of subclasses as well as interrelationships with other discrete structures. For example, two subclasses of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001015.png" />-matrices which arise are that of the barely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001016.png" />-matrices and the totally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001017.png" />-matrices.
+
\begin{equation*} M = \left( \begin{array} { c c c } { 1 } &amp; { - 1 } &amp; { 0 } \\ { 1 } &amp; { 1 } &amp; { - 1 } \\ { 1 } &amp; { 1 } &amp; { 1 } \end{array} \right) , \quad N = \left( \begin{array} { c c c c } { 1 } &amp; { 1 } &amp; { 1 } &amp; { - 1 } \\ { 1 } &amp; { 1 } &amp; { - 1 } &amp; { 1 } \\ { 1 } &amp; { - 1 } &amp; { 1 } &amp; { 1 } \end{array} \right) \end{equation*}
  
An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001018.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001019.png" /> is a barely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001021.png" />-matrix provided that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001022.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001023.png" />-matrix but if any column of it is deleted, the resulting matrix is not an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001024.png" />-matrix.
+
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 [[#References|[a1]]], [[#References|[a3]]] and [[#References|[a4]]].
  
An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001025.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001026.png" /> is a totally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001028.png" />-matrix provided that each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001029.png" />-submatrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001030.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001031.png" />-matrix.
+
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.
  
The two matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001033.png" /> above are examples of barely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001034.png" />-matrices. The matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001035.png" /> is also a totally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001036.png" />-matrix but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001037.png" /> is not since its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001038.png" />-submatrix made up of the first three columns is not an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001039.png" />-matrix. The matrix
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001040.png" /></td> </tr></table>
+
An $( m \times n )$-matrix $A$ is a totally $L$-matrix provided that each $( m \times m )$-submatrix of $A$ is an $L$-matrix.
  
is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001041.png" /> totally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001042.png" />-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
  
The property of being a barely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001043.png" />-matrix, or a totally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001044.png" />-matrix, imposes restrictions on the number of columns. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001045.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001046.png" /> barely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001047.png" />-matrix, then the number of columns is at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001048.png" />; further, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001049.png" /> has only non-negative entries, then the number of columns is at most
+
\begin{equation*} T = \left( \begin{array} { c c c c } { 1 } &amp; { 1 } &amp; { 1 } &amp; { 0 } \\ { 1 } &amp; { - 1 } &amp; { 0 } &amp; { 1 } \end{array} \right) \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001050.png" /></td> </tr></table>
+
is a $( 2 \times 4 )$ totally $L$-matrix.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001051.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001052.png" /> totally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001053.png" />-matrix, then the number of columns is at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001054.png" />. It has been shown that the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001055.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001056.png" /> totally <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001057.png" />-matrices can be obtained from the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001058.png" /> above by performing certain extension operations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001059.png" /> successively [[#References|[a2]]].
+
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
  
An important subclass of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001060.png" />-matrices for which there exist a great deal of literature is that of the square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l120/l120010/l12001062.png" />-matrices, which are also called sign-non-singular matrices.
+
\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 [[#References|[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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Bassett,  J. Maybee,  J. Quirk,  "Qualitative economics and the scope of the correspondence principle"  ''Econometrica'' , '''36'''  (1968)  pp. 544–563</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.A. Brualdi,  K.L. Chavey,  B.L. Shader,  "Rectangular L-matrices"  ''Linear Algebra Appl.'' , '''196'''  (1994)  pp. 37–61</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.A. Brualdi,  B.L. Shader,  "Matrices of sign solvable systems" , ''Tracts in Math.'' , '''116''' , Cambridge Univ. Press  (1995)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  V. Klee,  R. Ladner,  R. Manber,  "Sign-solvability revisited"  ''Linear Algebra Appl.'' , '''59'''  (1984)  pp. 131–157</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R. Manber,  "Graph-theoretical approach to qualitative solvability of linear systems"  ''Linear Algebra Appl.'' , '''48'''  (1982)  pp. 131–157</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P.A. Samuelson,  "Foundations of economic analysis" , ''Economic Studies'' , '''80''' , Harvard Univ. Press  (1947)</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  L. Bassett,  J. Maybee,  J. Quirk,  "Qualitative economics and the scope of the correspondence principle"  ''Econometrica'' , '''36'''  (1968)  pp. 544–563</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  R.A. Brualdi,  K.L. Chavey,  B.L. Shader,  "Rectangular L-matrices"  ''Linear Algebra Appl.'' , '''196'''  (1994)  pp. 37–61</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  R.A. Brualdi,  B.L. Shader,  "Matrices of sign solvable systems" , ''Tracts in Math.'' , '''116''' , Cambridge Univ. Press  (1995)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  V. Klee,  R. Ladner,  R. Manber,  "Sign-solvability revisited"  ''Linear Algebra Appl.'' , '''59'''  (1984)  pp. 131–157</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  R. Manber,  "Graph-theoretical approach to qualitative solvability of linear systems"  ''Linear Algebra Appl.'' , '''48'''  (1982)  pp. 131–157</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  P.A. Samuelson,  "Foundations of economic analysis" , ''Economic Studies'' , '''80''' , Harvard Univ. Press  (1947)</td></tr></table>

Latest revision as of 15:19, 1 July 2020

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)
How to Cite This Entry:
L-matrix. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=L-matrix&oldid=13301
This article was adapted from an original article by K. Chavey (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article