Re: [math-fun] Cyclic 0-1 determinants
Fred writes: << A matrix A of order n is "cyclic" when A[i,j] is a function only of (i-j)(mod n), and "0-1" when A[i,j] € {0,1}. What is a criterion for such a matrix to be singular (over the integers)? What is the maximum absolute value of its determinant as a function of n?
The paper (Determinants of binary circulant matrices. Proceedings of the ISIT, 2004) appears to discuss this question, but it requires a subscription or download fee. < http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/9423/29909/01365161.pd... >. Many references to this question mention "Hadamard bounds" or "Gram-Hadamard bounds" -- whatever that means -- on the size of a determinant. --Dan
Dan wrote:
The paper (Determinants of binary circulant matrices. Proceedings of the ISIT, 2004) appears to discuss this question, but it requires a subscription or download fee.
< http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/9423/29909/01365161.pd...
The "extended version", i.e. the one which actually contains proofs, is at http://www.math.unizh.ch/user/gmaze/Articles/detcirc2.pdf This paper explores the question of whether a circulant matrix whose entries are all {0,1} or all {-1,1} can have as large a determinant as is possible if you remove the "circulant" criterion (a.k.a. the Hadamard bound). I don't think it answers Fred's determinant question, but I just skimmed it. --Michael Kleber
.
Many references to this question mention "Hadamard bounds" or "Gram-Hadamard bounds" -- whatever that means -- on the size of a determinant.
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
On 5/29/07, Michael Kleber <michael.kleber@gmail.com> wrote:
Dan wrote:
The paper (Determinants of binary circulant matrices. Proceedings of the ISIT, 2004) appears to discuss this question, but it requires a subscription or download fee.
< http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/9423/29909/01365161.pd...
The "extended version", i.e. the one which actually contains proofs, is at http://www.math.unizh.ch/user/gmaze/Articles/detcirc2.pdf This paper explores the question of whether a circulant matrix whose entries are all {0,1} or all {-1,1} can have as large a determinant as is possible if you remove the "circulant" criterion (a.k.a. the Hadamard bound). I don't think it answers Fred's determinant question, but I just skimmed it.
--Michael Kleber
I tried to download the author's free version of this paper, via addresses mentioned by both Michael and Dan --- they're unreadable by my software. I've had this problem before with Postscript files which have been converted at the remote site. Thanks for the reference anyway, guys! WFL
On 5/29/07, Michael Kleber <michael.kleber@gmail.com> wrote:
The "extended version", i.e. the one which actually contains proofs, is at http://www.math.unizh.ch/user/gmaze/Articles/detcirc2.pdf This paper explores the question of whether a circulant matrix whose entries are all {0,1} or all {-1,1} can have as large a determinant as is possible if you remove the "circulant" criterion (a.k.a. the Hadamard bound). I don't think it answers Fred's determinant question, but I just skimmed it.
Thanks to everyone who pitched in to help sort out my attack of dodgy viewer software! This question turns out to have been well investigated: in particular, a "circulant" (what I called cyclic) matrix of order n is singular just when the coefficients along a row, mapped onto a polynomial in the natural fashion, correspond to a multiple of a (cyclotomic) factor of x^n - 1. E.g. since x+1 divides x^4-1, this "binary" (0-1) matrix is singular over the reals: [0 1 1 0] [1 1 0 0] [1 0 0 1] [0 0 1 1] Fred Lunnon
participants (3)
-
Dan Asimov -
Fred lunnon -
Michael Kleber