1
$\begingroup$

I have to write some code to detect if a large number of smallish (less than 20 by 20) square 0-1 matrices are singular over $\mathbb{R}$. As a circulant matrix is defined by its first row and its eigenvalues are a function of this row, is there a fast algorithm for this?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes, the eigenvalues of a circulant matrix are given by the discrete Fourier transform of the first column (http://en.wikipedia.org/wiki/Circulant_matrix).

Your matrix is singular, iff one eigenvalue is zero.

Hence, your matrix is singular if the FFT of the first column has one zero entry.

EDIT: eigenvalues are the FFT of the fist column not the first row (which has slightly different ordering).

$\endgroup$

You must log in to answer this question.