title: The complexity of the multiplication of two lower triangular matrices
body: <p>I know that the lower bound of the multiplication of two full matrices is Ω(n^2). <a href="https://en.wikipedia.org/wiki/Matrix_multiplication">Matrix multiplication</a></p>
  
  <p>I have been trying to prove that the lower bound of the multiplication of two lower triangular matrices using problem transformation method.</p>
  
  <p>My initial thinking is that to (1) transform the lower triangular matrix, (2) estimate the time complexity of such transformation.</p>
  
  <pre><code>T(lower_triangular_matrix_multiplication(n))+O(lower_triangular_matrix_transformation(n))&gt;Ω(full_matrix_multiplication(n)) = Ω(n^2)
  </code></pre>
  
  <p>Now, I only have to prove <code>O(lower_triangular_matrix_transformation(n))</code> and I need to make triangular matrix to be a full matrix so I just let this triangular matrix be multiplied by a variation of itself, say transpose, for simplicity.</p>
  
  <p>The reason is that the square of a lower triangular matrix is still a lower triangular matrix and a lower triangular matrix multiplied by its transposed variation is a "full matrix".</p>
  
  <p>So I only need to analyze the complexity of a triangular matrix multiplied by its transposed variation.</p>
  
  <p>Could anyone indicate if my thinking is "reasonable"?</p>