Let ${mathcal D}(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and $mathcal R(n) = {mathcal D}(n)/n^{n/2}$ be the ratio of ${mathcal D}(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on
${mathcal D}(n)$ and $mathcal R(n)$ in terms of $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h le n$. For example, $mathcal R(n) > (pi e/2)^{-d/2}$ if $1 le d le 3$, and $mathcal R(n) > (pi e/2)^{-d/2}(1 - d^2(pi/(2h))^{1/2})$ if $d > 3$. By a recent result of Livinskyi, $d^2/h^{1/2} to 0$ as $n to infty$, so the second bound is close to $(pi e/2)^{-d/2}$ for large $n$. Previous lower bounds tended to zero as $n to infty$ with $d$ fixed, except in the cases $d in {0,1}$. For $d ge 2$, our bounds are better for all sufficiently large $n$. If the Hadamard conjecture is true, then $d le 3$, so the first bound above shows that $mathcal R(n)$ is bounded below by a positive constant $(pi e/2)^{-3/2} > 0.1133$.
Let $D(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and ${mathcal R}(n) = D(n)/n^{n/2}$ be the ratio of $D(n)$ to the Hadamard upper bound. We give several new lower bounds on ${mathcal R}(n)$ in terms of $d$, where $n = h+d$, $h
$ is the order of a Hadamard matrix, and $h$ is maximal subject to $h le n$. A relatively simple bound is [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2} left(1 - d^2left(frac{pi}{2h}right)^{1/2}right) ;text{ for all }; n ge 1.] An asymptotically sharper bound is [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2} expleft(dleft(frac{pi}{2h}right)^{1/2} + ; Oleft(frac{d^{5/3}}{h^{2/3}}right)right).] We also show that [{mathcal R}(n) ge left(frac{2}{pi e}right)^{d/2}] if $n ge n_0$ and $n_0$ is sufficiently large, the threshold $n_0$ being independent of $d$, or for all $nge 1$ if $0 le d le 3$ (which would follow from the Hadamard conjecture). The proofs depend on the probabilistic method, and generalise previous results that were restricted to the cases $d=0$ and $d=1$.
We give upper and lower bounds on the determinant of a perturbation of the identity matrix or, more generally, a perturbation of a nonsingular diagonal matrix. The matrices considered are, in general, diagonally dominant. The lower bounds are best po
ssible, and in several cases they are stronger than well-known bounds due to Ostrowski and other authors. If $A = I-E$ is an $n times n$ matrix and the elements of $E$ are bounded in absolute value by $varepsilon le 1/n$, then a lower bound of Ostrowski (1938) is $det(A) ge 1-nvarepsilon$. We show that if, in addition, the diagonal elements of $E$ are zero, then a best-possible lower bound is [det(A) ge (1-(n-1)varepsilon),(1+varepsilon)^{n-1}.] Corresponding upper bounds are respectively [det(A) le (1 + 2varepsilon + nvarepsilon^2)^{n/2}] and [det(A) le (1 + (n-1)varepsilon^2)^{n/2}.] The first upper bound is stronger than Ostrowskis bound (for $varepsilon < 1/n$) $det(A) le (1 - nvarepsilon)^{-1}$. The second upper bound generalises Hadamards inequality, which is the case $varepsilon = 1$. A necessary and sufficient condition for our upper bounds to be best possible for matrices of order $n$ and all positive $varepsilon$ is the existence of a skew-Hadamard matrix of order $n$.
The Coxeter lattices, which we denote $A_{n/m}$, are a family of lattices containing many of the important lattices in low dimensions. This includes $A_n$, $E_7$, $E_8$ and their duals $A_n^*$, $E_7^*$ and $E_8^*$. We consider the problem of finding
a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexity $O(nlog{n})$ and the other with worst case complexity O(n) where $n$ is the dimension of the lattice. We show that for the particular lattices $A_n$ and $A_n^*$ the algorithms reduce to simple nearest point algorithms that already exist in the literature.
