(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)

[John Keith]

Update with one change and one new program.

The program C->LT has been replaced by C->M which turns a list of columns into a lower triangular matrix. C->LT can simply be replaced by C->M M->LT.

The new program TRICOL extracts a column or diagonal from a triangle. With the triangle (a list of lists) on level 2 and an integer n on level 1, the program returns the nth column as a list.

If n is negative, the nth column from the right is returned. If n = 0, the central column is returned. Since the central column consists of the central term from odd rows only, the central column will have half as many terms as the triangle has rows.

TRICOL requires ListExt 1.3 but can be re-written using DOLIST at some cost in speed and program size.

I am posting as a directory object again for convenience but all of the other programs are unchanged.

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\->M
  \<< 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\->AD
  \<< \->COL \->LIST 1.
    \<< AXL
    \>> DOLIST C\->M M\->LT
  \>>
  UNFLT
  \<< { } SWAP 1. \-> k
    \<<
      WHILE DUP SIZE k \>=
      REPEAT k SPLIT UNROT 1. \->LIST + SWAP 'k' INCR DROP
      END DROP
    \>>
  \>>
  TRICOL
  \<< I\->R \-> n
    \<<
      IF n 0 \=/
      THEN n ABS OVER SIZE SUB n 0. < { :: REV LMAP } IFT { n ABS GET } LMAP
      ELSE 1.
        \<< NSUB 2. MOD { NSUB 2. / GET } { DROP } IFTE
        \>> DOSUBS
      END
    \>>
  \>>
END