We now proceed to show that upper-triangular matrices are sufficient in terms of the grammar.
we need to show the following lemma: For each application of a single-initial rule A → B C, it is possible to create an entry for A by multiplying two upper-triangular matrices T 1 and T 2 , where T 1 contains an entry for B, and T 2 contains an entry for C. A nonterminal B appears in a cell above the diagonal if its row address is smaller than its column address, which in turn occurs if the leftmost endpoint of B appears in the row address rather than the column address.