Matrix completion and graph rigidity: exploiting surprising similarities

This master thesis addresses the problem of uniqueness of matrix completion by means of the graph rigidity results. The state of the art studies the existing results in both rigidity theory and matrix completion problem. It allows to determine that no author who addressed the question of the uniqueness of matrix completion using the results of graph rigidity, tried to directly reproduce the combinatorial results of Laman in two dimensions. A summary of Laman's results allows their good understanding in order to reproduce them in the context of matrix completion. A necessary and sufficient condition is found for the uniqueness of matrix completion. Finally, a pebble game algorithm allows to show whether a given matrix is uniquely completable.