两个下三角矩阵相乘的复杂度

Question

我知道两个满矩阵相乘的下限是Ω(n^2)。矩阵乘法 我一直在尝试证明两个下三角矩阵相乘的下限，使用问题转化方法。

我的初步想法是(1)转换下三角矩阵，(2)估计这种变换的时间复杂度。

T(lower_triangular_matrix_multiplication(n))+O(lower_triangular_matrix_transformation(n))>Ω(full_matrix_multiplication(n)) = Ω(n^2)

现在，我只需要证明O(lower_triangular_matrix_transformation(n))，我需要让三角矩阵成为一个满矩阵，所以我只需让这个三角矩阵乘以它的变形，比如转置，为了简单起见。

原因是一个下三角矩阵的平方仍然是一个下三角矩阵，并且一个下三角矩阵乘以它的转置变形是一个“满矩阵”。

所以我只需要分析一个三角矩阵乘以它的转置变形的复杂度。

请问我的想法是否“合理”？

- Alex Lin

---

仅仅是个想法，这不是更适合于数学StackExchange吗？这真的是一道数学问题，而不是一个编码/编程问题，虽然它具有算法性质。 - user650261

Answer 1

我不认为构建算法足以证明下界，因为仍然不排除存在具有更低复杂度的不同算法。

很明显，下限不会高于O（n ^ 2），因为通用乘法总是适用于下三角矩阵（ltm）。

现在，将任意矩阵转换为一个或多个ltm的任何转换本身都是O（n ^ 2）复杂度的操作，我们可能不能推断出不存在这样的算法。

你的推理大纲似乎表明增加复杂性遵循“正常”的算术规则。但事实并非如此！ 结果复杂性总是（至少是）算法部分复杂性的最大值。

所以你的推理似乎不可行。

你可以尝试以下之一：

1.构建具有较低复杂度的算法（通过存在性证明） 当目标是O（ltm）＜O（n ^ 2）时

2.找到一个复杂度＜O（n ^ 2）且产生ltm的变换。然后，任何具有较低复杂度的ltm乘法算法都将提供具有较低复杂度的任意矩阵的算法 这将违反您的初始命题。 然而，这需要一个足够低的复杂度的变换。如果这不知道。该参数无法使用。

对我来说，从T（）+ O（）> O（n ^ 2）的步骤似乎没有很好地奠定基础。 从而得出的结论仅需证明（O（ltm））是错误的。

- rpy

Answer 2

我认为解决方案可能是将A转化为A+A'。 转置和加法的操作复杂度均为O(n^2)。 因此，O（lower_triangular_matrix_transformation（n））= n ^ 2。 由于A A 的下限和（A + A'）（A + A'）的下限也为Ω（n ^ 2），T（lower_triangular_matrix_multiplication（n））> Ω（full_matrix_multiplication（n））-O（lower_triangular_matrix_transformation（n）），这意味着三角形矩阵的下限和完整矩阵的下限相同。

证毕。

- Alex Lin