(49g 50g) Triangular Matrix Utilities

[John Keith]

The programs described here are utility programs to convert between matrices and number triangles. The number triangles are in the form of lists of lists. The arrays that follow will be used to illustrate the use of these programs.

Code:


{{ 1 }
 { 1 1 }
 { 1 2  1 }
 { 1 3  3  1 }
 { 1 4  6  4  1 }
 { 1 5 10 10  5 1 }
 { 1 6 15 20 15 6 1 }
}

 
[[ 1 0  0  0  0 0 0 ]
 [ 1 1  0  0  0 0 0 ]
 [ 1 2  1  0  0 0 0 ]
 [ 1 3  3  1  0 0 0 ]
 [ 1 4  6  4  1 0 0 ]
 [ 1 5 10 10  5 1 0 ]
 [ 1 6 15 20 15 6 1 ]
]


{ {  1 }
  { -1  1 }
  {  1 -2   1 }
  { -1  3  -3   1 }
  {  1 -4   6  -4  1 }
  { -1  5 -10  10 -5  1 }
  {  1 -6  15 -20 15 -6 1 }
 }


{ { 1 1  1  1   1   1   1 }
  { 1 2  3  4   5   6   7 }
  { 1 3  6 10  15  21  28 }
  { 1 4 10 20  35  56  84 }
  { 1 5 15 35  70 126 210 }
  { 1 6 21 56 126 252 462 }
  { 1 7 28 84 210 462 924 }
}


[[ 1 1  1  1   1   1   1 ]

 [ 1 2  3  4   5   6   7 ]

 [ 1 3  6 10  15  21  28 ]

 [ 1 4 10 20  35  56  84 ]

 [ 1 5 15 35  70 126 210 ]

 [ 1 6 21 56 126 252 462 ]

 [ 1 7 28 84 210 462 924 ]
]


{ 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 }

The first program LT->M converts a number triangle to a lower triangular matrix, defined as a matrix where all entries above the main diagonal are zero. The second program M->LT converts in the opposite direction.

One use of these programs is to obtain the inverse of a number triangle, which can be used to implement the inverse of a transform associated with the triangle. As an example the sequence LT\->M INV M\->LT will convert Pascal's triangle (first illustration) into its inverse (3rd illustration).

The third program C->LT converts a list of lists interpreted as column vectors into a triangle. The reason behind this program is that many triangles are most easily created via their columns (aka diagonals).

The fourth program M->AD reads out a matrix by anti-diagonals into a triangle. The fourth illustration shows Pascal's triangle as a square matrix, and on can see the triangle as the upper left corner of the matrix.

With the examples above, the third and fourth programs appear to do the same thing due to the symmetry of Pascals triangle. With triangles that are not symmetric the results will be different.

The last program UNFLT un-flattens a list (last illustration) into a triangle. If the number of elements in the list are not a triangular number, the remaining elements of the list are discarded. As another example, a list of the numbers 1 through 10 will be converted into the first 4 rows of Floyd's triangle.

The command SPLIT in UNFLT requires the ListExt Library; if one prefers not to use external libraries, k SPLIT can be replaced by DUP 1. k SUB SWAP k 1.-OVER SIZE SUB.

Code:


DIR
  LT\->M
  \<< DUP SIZE \-> n
    \<< 1. n 1. -
      FOR j j DUP2 GET 0 n j - NDUPN \->LIST + PUT
      NEXT AXL
    \>>
  \>>
  M\->LT
  \<< AXL 1.
    \<< 1. NSUB SUB
    \>> DOSUBS
  \>>
  C\->LT
  \<< DUP SIZE \-> n
    \<< 1. n
      FOR k DUP k GET 0 k 1. - NDUPN \->LIST SWAP + 1. n SUB AXL SWAP
      NEXT DROP n COL\-> M\->LT 1.
      \<< REVLIST
      \>> DOLIST
    \>>
  \>>
  M\->AD
  \<< \->COL \->LIST 1.
    \<< AXL
    \>> DOLIST C\->LT
  \>>
  UNFLT
  \<< { } SWAP 1. \-> k
    \<<
      WHILE DUP SIZE k \>=
      REPEAT k SPLIT UNROT 1. \->LIST + SWAP 'k' INCR DROP
      END DROP
    \>>
  \>>
END

  TRIMAT.HP (Size: 478 bytes / Downloads: 5)