In mathematics applied to
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician
Gaspard Monge
Gaspard Monge, Comte de Péluse (; 9 May 1746 – 28 July 1818) was a French mathematician, commonly presented as the inventor of descriptive geometry, (the mathematical basis of) technical drawing, and the father of differential geometry. Dur ...
.
An ''m''-by-''n''
matrix
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the m ...
is said to be a ''Monge array'' if, for all
such that
:
one obtains
:
So for any two rows and two columns of a Monge array (a 2 × 2 sub-matrix) the four elements at the intersection points have the property that the sum of the upper-left and lower right elements (across the
main diagonal) is less than or equal to the sum of the lower-left and upper-right elements (across the
antidiagonal).
This matrix is a Monge array:
:
For example, take the intersection of rows 2 and 4 with columns 1 and 5.
The four elements are:
:
: 17 + 7 = 24
: 23 + 11 = 34
The sum of the upper-left and lower right elements is less than or equal to the sum of the lower-left and upper-right elements.
Properties
*The above definition is equivalent to the statement
:A matrix is a Monge array
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...