Problem understanding proof involving determinant

113 Views Asked by At

I have problems understanding Theorem 3.2, page 29 from Theory of Linear and Integer Programming. I don't understand (3): Let $M$ be a matrix in $\mathbb{Q}^{n\times n}$, and let $M_{ij} = a_{ij}/b_{ij}$ for $i$ and $j$ in $[1 \dots n]$, where $a_{ij}$ and $b_{ij}$ in $\mathbb{Z}$ are coprime and $b_{ij}>0$. Morever, let $\det (M) = a/b$, where $a$ and $b$ are coprime and $b >0$. Then

$$|\det(M)| \leq \prod_{i,j = 1}^{n} (|a_{ij}| +1)\,.$$

Any ideas? Does this follow from the Laplace expansion?

1

There are 1 best solutions below

0
On BEST ANSWER

First of all, notice that $\sum_{i=1}^n|a_{ij}|^2\leq \prod_{i=1}^n (|a_{ij}|+1)^2$(Expand the right side.)

Now, by Hadamard inequality we have $|\det(M)|\leq\prod_{j=1}^n\sqrt{\sum_{i=1}^n|m_{ij}|^2}$

Now, by hypothesis $|m_{ij}|\leq|a_{ij}|$. Thus, $|\det(M)|\leq\prod_{j=1}^n\sqrt{\sum_{i=1}^n|a_{ij}|^2}$.

Finally, by our first inequality we obtain $|\det(M)|\leq\prod_{j=1}^n\sqrt{\sum_{i=1}^n|a_{ij}|^2}\leq \prod_{j=1}^n\prod_{i=1}^n (|a_{ij}|+1)$.