Totally Monotone Matrix

释义 Definition

Totally monotone matrix（全单调矩阵）：一种具有特殊“单调性”性质的矩阵。直观地说，当你在不同的行里寻找每行的最小值（或最大值）所在的列位置时，这些列索引会随着行号单调不减（不会往回跳）。该性质常用于设计算法，以更快地在矩阵中找行最值位置。
（注：不同文献可能以“行最小值”或“行最大值”的版本叙述；核心是“最值列索引随行单调”。）

发音 Pronunciation (IPA)

/ˈtoʊtəli ˈmɑːnəˌtoʊn ˈmeɪtrɪks/

例句 Examples

A totally monotone matrix lets us find row minima faster than checking every entry.
全单调矩阵能让我们比逐个检查元素更快地找到每一行的最小值。

Using the SMAWK algorithm, we can compute all row argmins in a totally monotone matrix in linear time relative to its size.
使用 SMAWK 算法，我们可以在与矩阵规模线性相关的时间内，计算全单调矩阵每一行最小值所在的列（argmin）。

词源 Etymology

该术语由三部分组成：totally（完全地）+ monotone（单调的）+ matrix（矩阵）。其中 monotone 源自希腊语词根 *mono-*（“单一”）与 tonos（“音调/张力”），引申出“朝一个方向变化、不起伏”的含义；在算法与离散数学语境中，“totally monotone”强调这种单调性不是偶然出现，而是对整类行/列比较结构普遍成立，从而可被算法系统利用。

相关词 Related Words

• Monge Array
• SMAWK Algorithm
• Argmin
• Convexity
• Dynamic Programming
• Matrix
• Monotonicity
• Submatrix

文学与名著中的用例 Literary Works

• Aggarwal, Klawe, Moran, Shor, Wilber: “Geometric Applications of a Matrix-Searching Algorithm” （提出并推广用于全单调矩阵的经典搜索思想，关联 SMAWK 线性时间求行最值）
• Atallah & Blanton (eds.): Algorithms and Theory of Computation Handbook（算法工具书中常在“矩阵搜索 / Monge 与全单调结构”处出现）
• Preparata & Shamos: Computational Geometry: An Introduction（计算几何与相关优化问题中，常引用全单调/Monge 结构以加速计算）
• 相关研究综述与教材章节：关于 Monge arrays、矩阵搜索（matrix searching）与 SMAWK 的章节与论文中频繁出现该术语