# Maximum determinant of a $(0,1)$-matrix [duplicate]

Suppose that the elements of an n- order determinant are either $$0$$ or $$1$$, I wonder the maximum and the minimum of the determinant.

Furthermore, I wonder all possible values of it. What if I change the question that the elements are either $$1$$ or $$-1$$?

• What has your question to do with number-theory? Dec 29, 2019 at 15:13
• First question: math.stackexchange.com/questions/425417/… Dec 29, 2019 at 15:19
• @José Carlos Santos My opinion is that the question is closely related to integer combination. Therefore, the possible solutions might to do with number theory. Dec 29, 2019 at 15:26

Closed forms for the maximum and minimum are not known, but there are decent bounds available. For a $$(0,1)$$ $$n\times n$$ matrix $$A$$, we have $$|\det A|\leq \frac{(n+1)^{(n+1)/2}}{2^n}$$ and for a $$(-1,1)$$ matrix the maximum value is $$2^{n-1}$$ times the maximum $$(0,1)$$ value. See mathworld for more info.

Note that in both cases the minimum value is the additive inverse of the maximum value for $$n\geq 2$$, since we can permute two rows to achieve this value.

The determinant of a matrix $$A=a_{i,j}$$,$$1 \le i,j \le n$$ is given by (where $$S_n$$ is the set of all permutations of $$\{1,\ldots,n\}$$ and $$\operatorname{sgn}(\sigma)$$ is the sign of a permutation $$\sigma \in S_n$$ ($$-1$$ for odd, $$1$$ for even)

$$\det(A)=\sum_{\sigma \in S_n}\operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i, \sigma(i)}$$

so an alternating sum of terms, which are each products of $$n$$ terms. All these product terms are $$0$$ or $$1$$, so the greatest value is achieved when all even permutations yield $$1$$ while odd permutations yield $$0$$, e.g. So $$\frac{n!}{2}$$ is best (not sure if it's reachable though).

With $$1,-1$$ it's more complicated. Maybe check out this question or this reference

• Since it is tough to calculate the best approximation, I wonder whether it is proved to be a "Polynomial problem" or not. Dec 29, 2019 at 15:41
• @TamshinDion the mathworld article (second link) shows it's well understood ven in the case of $-1,1$ matrices, where we have Hadamard matrices to find the max. The max itself is easier to find. Dec 29, 2019 at 15:44
• .Thanks for mentioning me that. Link: mathworld.wolfram.com/HadamardMatrix.html Dec 29, 2019 at 15:53
• @TamshinDion rather mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html for the more general case. Dec 29, 2019 at 15:57