2
$\begingroup$

Let $A = (a_{ij})_n$ where $a_{ij} \ge 0$ for $i,j=1,2,\ldots,n$ and $\sum_{j=1}^n a_{ij} \le 1$ for $i = 1,2,\ldots,n$.
Show that $|\det(A)| \le 1$.

Should I use the definition of matrix:

$$\det(A)=\sum \textrm{sgn}(\sigma)a_{1,\sigma(1)}a_{2,\sigma(2)}...a_{n,\sigma(n)}$$

I don't understand what is $a_{i,\sigma(i)}$ ? Where $i=1,2, \ldots,n$. Or is there another way to solve it?

$\endgroup$
6
$\begingroup$

You can prove that by induction on the dimension $n$ of the matrix. It is clearly true for $n = 1$.

Now assume that $n > 1$ and the statement is true for all matrices of dimension $(n-1, n-1)$. Using the Laplace formula, you have $$ \det(A) = \sum_{j=1}^n a_{1j} \det(A_j) $$ where $A_1, ..., A_n$ are submatrices of the dimension $(n-1, n-1)$ which have the same properties as $A$: All entries are positive and the row sums are less or equal to one, so $|\det(A_j)| \le 1$ for $j=1,..., n$.

Then $$ |\det(A)| \le \sum_{j=1}^n a_{1j} |\det(A_j)| \le \sum_{j=1}^n a_{1j} \le 1 $$

$\endgroup$
  • $\begingroup$ But how can we take |det(Aj)|≤1 directly? It should has more explaination. $\endgroup$ – Sokserey Man Dec 4 '15 at 7:20
  • $\begingroup$ @SoksereyMan: It is a proof by "mathematical induction". $A_j$ is a "smaller" matrix with the same properties, therefore you can assume the statement to be true for $A_j$. $\endgroup$ – Martin R Dec 4 '15 at 7:52
  • 1
    $\begingroup$ @Martin R: Nice ! This seems to work for the permanent too, which in this case is clearly larger than the absolute value of the determinant. $\endgroup$ – Orest Bucicovschi Dec 4 '15 at 9:49
  • $\begingroup$ @SoksereyMan Do you or do you not need to use Leibniz' formula? $\endgroup$ – BCLC Dec 4 '15 at 11:22
2
$\begingroup$

Here is the sneaky approach:

First note, we can decide whether we want the column-sums or the row-sums to be $\leq 1$, since we can of course transpose our matrix. I want the column-sums to be $\leq 1$.

The $1$-norm $\| \cdot \|_1$ on $\mathbb C^n$ induces via

$$\| A \| := \sup_{x \neq 0} \frac{\|Ax\|_1}{\|x\|_1}$$

the column-sum norm on the $n \times n$-matrices. The assumption is precisely $\|A\| \leq 1$ then.

For any $x \in \mathbb C^n$ we have $\|Ax\|_1 \leq \|A\|\|x\|_1 \leq \|x\|_1$. This holds in particular for any eigenvector of $A$, which shows that any (possibly complex) eigenvalue $\lambda$ of $A$ satisfies $|\lambda| \leq 1$. This shows the assertion, since the determinant is obtained as the product of all eigenvalues.


We also have a geometric reason: The edges of the unit cubes are mapped into the unit cube, hence any convex combination of them is mapped into the unit cube. This shows $A[0,1]^n \subset [0,1]^n$. Since the determinant is geometrically defined to be the volume of the image of the unit cube, we immediately get the desired result.

$\endgroup$
0
$\begingroup$

Correct. Use Leibniz formula for determinants. See here for an example.

As for the a's (from the link above, formatting mine):

Here the sum is computed over all permutations σ of the set {1, 2, ..., n}. A permutation is a function that reorders this set of integers. The value in the ith position after the reordering σ is denoted $σ_i$. For example, for n = 3, the original sequence 1, 2, 3 might be reordered to σ = [2, 3, 1], with $σ_1 = 2, σ_2 = 3$, and $σ_3 = 1$.

$\endgroup$
  • $\begingroup$ Maybe it's hard for me to understand because I learned very little about it. $\endgroup$ – Sokserey Man Dec 4 '15 at 6:28
0
$\begingroup$

Just take modulus the determinant expression you wrote. Note each term on the right under sum can be bounded by using G.M. $\le$ A.M.

$\endgroup$
  • $\begingroup$ Wouldn't that require that $\sum_{j=1}^n a_{j\sigma(j)} \le 1$ ? Can one conclude that from $\sum_{j=1}^n a_{ij} \le 1$ ? $\endgroup$ – Martin R Dec 4 '15 at 7:14
  • $\begingroup$ Is that would. Actually I didn't notice ur ans. $\endgroup$ – Mahbub Alam Dec 4 '15 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.