Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-012 | 2nd February 1998 00:00

Determinant: Old Algorithms, New Insights

RSS-Feed




TR98-012
Authors: Meena Mahajan, V. Vinay
Publication: 18th February 1998 12:23
Downloads: 1406
Keywords: 


Abstract:


In this paper we approach the problem of computing the characteristic
polynomial of a matrix from the combinatorial viewpoint. We present
several combinatorial characterizations of the coefficients of the
characteristic polynomial, in terms of walks and closed walks of
different kinds in the underlying graph. We develop algorithms based
on these characterizations, and show that they tally with well-known
algorithms arrived at independently from considerations in linear
algebra.



ISSN 1433-8092 | Imprint