Matrix Reduction  Practice  Problems

MATH  384
Due Tuesday, April 30

1. Reduce the following matrix using left-to-right column additions with mod 2 arithmetic.

You may do this by specifying each column addition or using code you wrote in class.

matrix={{0,0,0,0,1,1,1,0,1,1,0,1,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0},{0,0,0,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0},{0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1},{0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1},{1,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0},{1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0}};
MatrixForm[matrix]

2. Compute the persistent homology pairings for simplices in the Vietoris-Rips complex obtained from the following point cloud.

You must first compute the Vietoris-Rips filtration (use code provided in class on April 25) and its boundary matrices (∂_1) and (∂_2). Reduce these boundary matrices and identify the pairings of simplices. You should specify which points and edges are paired, which edges and triangular faces are paired, and which simplices generate homology.

points={{0.472,0.233},{0.0154,0.720},{0.412,0.987},{0.616,0.788},{0.927,0.818},{0.879,0.082}}

3. What is the computational complexity of the matrix reduction algorithm from class?

For this, suppose matrix M has c columns and r rows. Let n=max(r,c). How many operations are required to reduce matrix M using our algorithm? Express your answer in terms of n.