Results 1 to 5 of 5

Math Help - Determinant

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    24

    Determinant

    Let A = [a_{ij}]_{n_x n} be a matrix with nonnegative entries such that \sum\limits^n_{i=1}\sum\limits^n_{j=1}a_{ij}=n
    Prove that |det\, A|\leq 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Julius View Post
    Let A = [a_{ij}]_{n_x n} be a matrix with nonnegative entries such that \sum\limits^n_{i=1}\sum\limits^n_{j=1}a_{ij}=n
    Prove that |det\, A|\leq 1
    In \mathbb{R}^n, let z = (1,1,\ldots,1)^{\textsc{t}}, and let C be the unit cube [0,1]\times[0,1]\times\cdots\times[0,1]. Then AC \subseteq \textstyle \bigl[0,\sum a_{1j}\bigr]\times\Bigl[0,\sum a_{2j}\Bigr]\times\cdots\times\Bigl[0,\sum a_{nj}\Bigr].

    By the change of variables theorem, with y = Ax, the integral of the inner product of y with z over the region AC is given by

    \int_C\langle Ax,z\rangle|\text{det}\,A|\,dx = \int_{AC}\langle y,z\rangle\,dy.

    The left side is \int_0^1\!\!\!\int_0^1\!\!\!\!\cdots\!\!\!\int_0^1  \Bigl(\sum a_{i1}x_1 + \ldots + \sum a_{in}x_n\Bigr)|\text{det}\,A|\,dx_1\ldots dx_n = \tfrac12\sum_{i,j=1}^n a_{ij}|\text{det}\,A| = \tfrac12|\text{det}\,A|.

    The right side is \int_{AC}\langle y,z\rangle\,dy \leqslant \int_0^{\sum a_{1j}}\!\!\! \int_0^{\sum a_{2j}}\mkern-30mu\cdots\int_0^{\sum a_{nj}}\!\!\!(y_1+\ldots+y_n)\,dy_1\ldots dy_n = \tfrac12\sum_{i,j=1}^n a_{ij} = \tfrac12.

    Putting the two together, you see that |\text{det}\,A| \leqslant 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    This is a pretty proof, but as such it would actually prove that |\det A|\leq 1 for every nonnegative matrix A, wouldn't it? I have some concerns about this last line:
    Quote Originally Posted by Opalg View Post
    The right side is \int_{AC}\langle y,z\rangle\,dy \leqslant  \int_0^{\sum a_{1j}}\!\!\! \int_0^{\sum  a_{2j}}\mkern-30mu\cdots\int_0^{\sum  a_{nj}}\!\!\!(y_1+\ldots+y_n)\,dy_1\ldots dy_n = \tfrac12\sum_{i,j=1}^n  a_{ij} = \tfrac12.
    One has
    \int_0^{A_1}\cdots\int_0^{A_n}(y_1+\cdots+y_n)dy_1  \cdots dy_n=\frac{1}{2}(A_1)^2 A_2\cdots A_n+\cdots+\frac{1}{2}A_1\cdots A_{n-1}(A_n)^2 =\frac{1}{2}A_1\cdots A_n(A_1+\cdots+A_n),
    which is much larger.

    A possible proof: define \widetilde{A} by dividing each line of the matrix A by its sum, hence making it a "stochastic" matrix. We have \det A=\prod_i\sum_j a_{ij}\det\widetilde{A}, and by the arithmetic-geometric inequality, the prefactor (which is positive) is less than \left(\frac{1}{n}\sum_i\sum_j a_{ij}\right)^n\leq 1, so that we are reduced to proving that |\det \widetilde{A}|\leq 1. This is a classical fact, which one can prove by looking at the complex eigenvectors: if \widetilde{A}Y=\lambda Y, applying the triangle inequality at the line corresponding to the largest entry |y_i|, one gets |\lambda|\leq 1. Or there is also a geometrical proof along the exact same lines as yours! since A_1\cdots A_n=1 in this case
    Last edited by Laurent; March 14th 2010 at 07:20 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Laurent View Post
    This is a pretty proof, but as such it would actually prove that |\det A|\leq 1 for every nonnegative matrix A, wouldn't it?
    Yes, that was careless. I was starting from the fact that the linear transformation with matrix A dilates volumes by a factor |\text{det}\,A|, and I was looking for a geometric reason why the image of the unit cube under that transformation should have volume at most 1. I still think that method should work, though obviously my approach didn't. However, it stimulated Laurent into providing a correct proof, so some good came of it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Opalg View Post
    I still think that method should work
    Actually it works in a much simpler way than what you did! (and with the arithmetic-geometric inequality):

    We have
    A[0,1]^n\subset \bigg[0,\sum_j a_{1j}\bigg]\times \cdots\times\bigg[0,\sum_j a_{nj}\bigg],
    hence, simply taking the volume of each side:
    |\det A|\leq \prod_i \sum_j a_{ij}.
    By the arithmetic-geometric inequality, the right-hand side is less than \left(\frac{1}{n}\sum_{i,j}a_{ij}\right)^{n}. Under the assumption of the question, this equals 1. qed
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Determinant help
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: January 16th 2010, 01:55 AM
  2. Determinant
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 10th 2009, 07:24 PM
  3. Determinant 3
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 28th 2009, 12:53 PM
  4. Determinant 2
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 28th 2009, 02:34 AM
  5. Determinant
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 28th 2009, 02:10 AM

Search Tags


/mathhelpforum @mathhelpforum