METHOD VIA A POLYNOMIAL APPROACH TO MATRIX AND HYPERMATRIX ALGEBRA

We discuss a polynomial encoding which provides a unified framework for discussing the algebra and the spectral analysis of matrices and hypermatri-ces. In addition to describing some algorithms for performing orthogonaliza-tion and spectral analysis of hypermatrices, we discuss some computational aspects, more specifically the important role of symmetries in Alon’s Combi-natorial Nullstellensatz method for solving combinatorial problems. ii Acknowledgements I am incredibly grateful to my advisors Ahmed Elgammal, Vladimir Retakh, for their guidance and encouragement. Their influence on me has been tremen-dous, and I could not ask for better dissertation mentors. I am indebted to Doron Zeilberger and Mario Szegedy for numerous insightful comments and suggestions which have improved this work significantly. I am also grateful to Michael Saks, Henry Cohn, Eileen Kowler, William Massey, Lek-Heng Lim, Neil Sloane and Avi Wigderson for their valuable time and assistance. I very much appreciate each of their contributions to this work. I owe many thank