# Past Computational Mathematics and Applications Seminar

In addition to the announced topic of Pascal Matrices (abstract below) we will speak briefly about more recent work by Per-Olof Persson on generating simplicial meshes on regions defined by a function that gives the distance from the boundary. Our first goal was a short MATLAB code and we just submitted "A Simple Mesh Generator in MATLAB" to SIAM.

This is joint work with Alan Edelman at MIT and a little bit with Pascal. They had all the ideas.

Put the famous Pascal triangle into a matrix. It could go into a lower triangular L or its transpose L' or a symmetric matrix S:

[ 1 0 0 0 ] | [ 1 1 1 1 ] | [ 1 1 1 1] | |||

L = | [ 1 1 0 0 ] | L' = | [ 0 1 2 3 ] | S = | [ 1 2 3 4] |

[ 1 2 1 0 ] | [ 0 0 1 3 ] | [ 1 3 6 10] | |||

[ 1 3 3 1 ] | [ 0 0 0 1 ] | [ 1 4 10 20] |

These binomial numbers come from a recursion, or from the formula for i choose j, or functionally from taking powers of (1 + x).

The amazing thing is that L times L' equals S. (OK for 4 by 4) It follows that S has determinant 1. The matrices have other unexpected properties too, that give beautiful examples in teaching linear algebra. The proof of L L' = S comes 3 ways, I don't know which you will prefer:

1. By induction using the recursion formula for the matrix entries.

2. By an identity for the coefficients i+j choose j in S.

3. By applying both sides to the column vector [ 1 x x^{2} x^{3} ... ]'.

The third way also gives a proof that S^{3} = -I but we doubt that result.

The rows of the "hypercube matrix" L^{2} count corners and edges and
faces and ... in n dimensional cubes.

From the point of view of a numerical analyst, I will describe some algorithms for:

- clustering data points based on pairwise similarity,
- reordering a sparse matrix to reduce envelope, two-sum or bandwidth,
- reordering nodes in a range-dependent random graph to reflect the range-dependency,

and point out some connections between seemingly disparate solution techniques. These datamining problems arise across a range of disciplines. I will mention a particularly new and important application from bioinformatics concerning the analysis of gene or protein interaction data.