Monge array (Monge matrix)

Monge array (Monge matrix)

---

   Definition   

  아래와 같은 조건을 갖는 m-by-n matrix 이다.

  의 조건에 대해서

  를 만족하는 matrix 를 Monge array 혹은 Monge matrix 라고 한다.

---

   Example   

6 by 5 matrix

  위 사진을 보면 Monge array 의 정의를 직관적으로 볼 수 있다. 표시해둔 보라색, 연두색 점들로 예를 들어보자. 이 점들의 i, j, k, l 은 다음과 같다.

• i = 2
• j = 3
• k = 4
• l = 5

  A[2, 3] + A[4, 5] <= A[2, 5] + A[4, 3]

  16 + 7 <= 23 + 6

  23 <= 29 이므로 Monge array 의 조건을 만족한다.

  보면 다른 임의의 점들도 Monge array 의 조건을 만족함을 알 수 있다.