2 つの完全な行列の乗算の下限が Ω(n^2) であることはわかっています。行列乗算
問題変換法を使用して、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))必要があるだけであり、三角行列を完全な行列にする必要があるため、簡単にするために、この三角行列にそれ自体のバリエーション、たとえば転置を掛けるだけです。
その理由は、下三角行列の 2 乗は依然として下三角行列であり、その転置された変化を乗じた下三角行列は「完全な行列」だからです。
したがって、三角行列に転置されたバリエーションを乗じた複雑さを分析するだけで済みます。
私の考えが「合理的」であるかどうかを誰かが示すことができますか?