# Upper Bound On A Determinant

In competitive prediction it is often necessary to find upper bounds for the determinant  , which, by the Sylvester identity, equals  . Let us assume that the size of  is  and the columns of  are vectors  ; it is natural for the purposes of machine learning to formulate bounds involving properties of these vectors.

# Infinity Norm

A bound in terms of the infinity norms of  was obtained in [Vovk]. Recall that the infinity norm of a vector  is the maximum absolute value of its coordinates,  .

The determinant of a positive definite matrix does not exceed the product of its diagonal elements (see, e.g., [Beckenbach and Bellman, Chapter 2, Theorem 7]. Let  ; in other words,  is the maximum absolute value of an element of  . A diagonal element of  does not exceed  and we get the bound In [Cesa-Bianchi et al] a bound in terms of the quadratic norms of  was obtained. The quadratic (or Euclidean) norm of a vector  is given by  .

The determinant of a matrix is the product of its (generally speaking complex) eigenvalues counting multiplicities. If  are the eigenvalues of  , then the eigenvalues of  are  and  .

The sum of eigenvalues  equals the trace  and  . Indeed, the matrices  and  (provided they exist) have the same non-zero eigenvalues counting multiplicities while zero eigenvalues do not contribute to the trace. Alternatively one can verify the equality  by a straightforward calculation, see, e.g., [Axler, Proposition 10.9 (p. 219)]. The matrix  is the Gram matrix of vectors  and the elements on its diagonal are the squared quadratic norms of the vectors. Letting  we get  .

The problem has reduced to obtaining an upper bound on the product of some positive numbers with a known sum. The inequality of arithmetic and geometric means implies that Combining this with the bound on the trace yields # Comparison

Let us compare the bounds. For every vector  we have  (the inequality is tight: for a vector of equal coordinates  it is an equality) and therefore for any array of vectors  we get We conclude that the quadratic norm bound is not weaker than the infinity norm bound.

# References

[Vovk] V. Vovk. Competitive on-line statistics. International Statistical Review, 69(2):213-248, 2001.

[Beckenbach and Bellman] E.F.Beckenbach and R.E.Bellman. Inequalities. Springer, 1961.

[Cesa-Bianchi et al] N.Cesa-Bianchi, A.Conconi, and C.Gentile. A second-order perceptron algorithm. SIAM Journal on Computing, 34(3):640-668, 2005.

[Axler] S.Axler. Linear Algebra Done Right. Springer, 2nd edition, 1997.