ในคณิตศาสตร์ประยุกต์กับวิทยาการคอมพิวเตอร์อาร์เรย์มองจ์หรือเมทริกซ์มองจ์คือวัตถุทางคณิตศาสตร์ที่ตั้งชื่อตามผู้ค้นพบ คือกัสปาร์ มองจ์นัก คณิตศาสตร์ชาวฝรั่งเศส

เมทริกซ์ ขนาด m x n เรียกว่าอาร์เรย์ Mongeถ้าสำหรับทุกๆที่ ทำให้^{[ 1 ]} กล่าวอีกนัยหนึ่ง สำหรับสองแถวและสองคอลัมน์ใดๆ ของอาร์เรย์ Monge องค์ประกอบทั้งสี่ที่จุดตัด (เมทริกซ์ย่อย 2 × 2) มีคุณสมบัติที่ผลรวมขององค์ประกอบด้านบนซ้ายและด้านล่างขวา (บนแนวทแยงหลัก ) น้อยกว่าหรือเท่ากับผลรวมขององค์ประกอบด้านล่างซ้ายและด้านบนขวา (บนแนวทแยงตรงข้าม ) ${\displaystyle i,j,k,\ell }$$${\displaystyle 1\leq i<k\leq m{\text{ และ }}1\leq j<\ell \leq n,}$$$${\displaystyle A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].}$$

เมทริกซ์นี้เป็นอาร์เรย์ Monge:

${\displaystyle {\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}}$

ตัวอย่างเช่น พิจารณาจุดตัดของแถวที่ 2 และ 4 กับคอลัมน์ที่ 1 และ 5 จะได้องค์ประกอบทั้งสี่ดังนี้ ผลรวมขององค์ประกอบด้านบนซ้ายและด้านล่างขวา (17 + 7 = 24) จะไม่มากกว่าผลรวมขององค์ประกอบด้านล่างซ้ายและด้านบนขวา (23 + 11 = 34) $${\displaystyle {\begin{bmatrix}17&23\\11&7\end{bmatrix}}.}$$

• คำจำกัดความข้างต้นเทียบเท่ากับข้อความดังกล่าว

เมทริกซ์เป็นอาร์เรย์ Monge ก็ต่อเมื่อ สำหรับทุกและ. ^{[ 1 ]}${\displaystyle A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]}$${\displaystyle 1\leq i<m}$${\displaystyle 1\leq j<n}$

• อาร์เรย์ย่อยใดๆ ที่ได้จากการเลือกแถวและคอลัมน์บางส่วนจากอาร์เรย์ Monge ดั้งเดิม จะยังคงเป็นอาร์เรย์ Monge อยู่ดี
• ผลรวมเชิงเส้นใดๆที่มีสัมประสิทธิ์ไม่เป็นลบของอาร์เรย์ Monge นั้น ก็เป็นอาร์เรย์ Monge ด้วยเช่นกัน
• อาร์เรย์ Monge ทุกอาร์เรย์เป็นโมโนโทนโดยสมบูรณ์ หมายความว่าค่าต่ำสุดของแถวจะเกิดขึ้นในลำดับที่ไม่ลดลงของคอลัมน์ และคุณสมบัติเดียวกันนี้เป็นจริงสำหรับซับอาร์เรย์ทุกอัน คุณสมบัตินี้ช่วยให้สามารถค้นหาค่าต่ำสุดของแถวได้อย่างรวดเร็วโดยใช้อัลกอริธึม SMAWKหากคุณทำเครื่องหมายด้วยวงกลมที่ค่าต่ำสุดซ้ายสุดของแต่ละแถว คุณจะพบว่าวงกลมของคุณเคลื่อนลงไปทางขวา นั่นคือ ถ้าแล้วสำหรับทุก ใน ทำนองเดียวกัน หากคุณทำเครื่องหมายที่ค่าต่ำสุดบนสุดของแต่ละคอลัมน์ วงกลมของคุณจะเคลื่อนไปทางขวาและลงล่าง ค่าสูงสุดของแถวและคอลัมน์จะเคลื่อนไปในทิศทางตรงกันข้าม คือ ขึ้นไปทางขวาและลงไปทางซ้าย${\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}$${\displaystyle f(j)\leq f(j+1)}$${\displaystyle 1\leq j<n}$
• แนวคิดเรื่องอาร์เรย์ Monge แบบอ่อนได้รับการเสนอขึ้น อาร์เรย์ Monge แบบอ่อนคือเมทริกซ์จัตุรัสขนาดn x nที่สอดคล้องกับคุณสมบัติของ Monge เฉพาะสำหรับค่า n ใดๆเท่านั้น${\displaystyle A[i,i]+A[r,s]\leq A[i,s]+A[r,i]}$${\displaystyle 1\leq i<r,s\leq n}$
• เมทริกซ์ Monge เป็นอีกชื่อหนึ่งของฟังก์ชันย่อยโมดูลาร์ของตัวแปรไม่ต่อเนื่องสองตัว กล่าวคือA เป็น เมทริกซ์ Monge ก็ต่อเมื่อA [ i , j ] เป็นฟังก์ชันย่อยโมดูลาร์ของตัวแปร  i , j

เมทริกซ์ Monge มีการประยุกต์ใช้ในปัญหา การหาค่าเหมาะสมที่สุดเชิงการจัดเรียง :

• เมื่อปัญหาพนักงานขายเดินทางมีเมทริกซ์ต้นทุนซึ่งเป็นเมทริกซ์ Monge จะสามารถแก้ได้ในเวลากำลังสอง^{[ 1 ] [ 2 ]}
• เมทริกซ์จัตุรัส Monge ที่สมมาตรเกี่ยวกับเส้นทแยงมุมหลักเรียกว่าเมทริกซ์ Supnick (ตั้งชื่อตามFred Supnick ) การรวมเชิงเส้นของเมทริกซ์ Supnick ใดๆ ก็ตามถือเป็นเมทริกซ์ Supnick เช่นกัน^{[ 1 ]}และเมื่อเมทริกซ์ต้นทุนในปัญหาพนักงานขายเดินทางเป็นเมทริกซ์ Supnick คำตอบที่เหมาะสมที่สุดจะเป็นเส้นทางที่กำหนดไว้ล่วงหน้า ซึ่งไม่ได้รับผลกระทบจากค่าเฉพาะภายในเมทริกซ์^{[ 2 ]}