Topics in combinatorial matrix theory

In the finite-time average consensus problem, the goal is to make the agents meet at the average of their initial positions in a finite number of steps, with the constraint that each agent receives at each step a limited number of positions. In this framework, the De Bruijn graphs have turned out to be an optimal communication strategy, in the sense that all the agents meet at the desired place after a minimum number of steps. More generally, the binary matrix roots of the all-ones matrix are all optimal strategies. However, apart from the De Bruijn matrix, these matrix roots are nowadays still unknown. Our first results are then about the binary roots of the matrix of all ones and in particular about their relation with the De Bruijn matrix. Our research on the average consensus led us to the minimum rank problems. Given a graph and a set of matrices that have a pattern matching the structure of the graph, it is asked to find the minimum possible rank for a matrix in this set. Several graph invariants give lower and upper bounds on the minimum rank. In particular, the so-called zero forcing number gives the exact value of the minimum rank for each tree. However, few algorithms exist that compute the zero forcing number. Our next results are then devoted to the computation of this graph invariant. We moreover apply it to determine if a networked system is controllable whatever the interaction strengths between the agents. Solving a very large linear system is a problem encountered in many different areas of science and engineering. The current direct and iterative algorithms that solve a linear system generally have a computational complexity that is prohibitive when the system is large. Consequently, one of the most recent research areas is to develop nearly-linear time solvers. Our last results contribute to that exciting challenge.