Return to Answer

By using the arithmetic-geometric mean inequality, if each entry $a_{i,j}$ in $A$ is positive, we can bound several quantities related to $A$ below by the product $\prod_{i,j}a_{i,j}$. The geometric-arithmetic mean inequality states that $(x_1\dots x_n)^{1/n}\leq\frac{1}{n}(x_1+\dots+x_n)$ whenever $x_1,\dots,x_n$ are non-negative. Therefore, $n(x_1\dots x_n)^{1/n}\leq x_1+\dots+x_n$ whenever $x_1,\dots,x_n$ are non-negative.

Suppose $A$ is a matrix with non-negative entries. Then

$$\text{per}(A)=\sum_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)}\geq n!\cdot(\prod_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)})^{1/n!}=n!\cdot\big((\prod_{i,j}a_{i,j})^{(n-1)!}\big)^{1/n!}$$ $$=n!\cdot(\prod_{i,j}a_{i,j})^{1/n}.$$

Here, equality is reached if and only if every entry in $A$ is the same. While this inequality is easy to prove, the Van der Waerden's conjecture is a result that was proven in 1980 that strengthens this inequality.

If $A$ is doubly stochastic, then by again applying the geometric-arithmetric mean inequality, we obtain $\prod_{i,j}a_{i,j}\leq n^{-n^2}.$

Van der Waerden's conjecture states that $$n!\cdot(\prod_{i,j}a_{i,j})^{1/n}\leq\frac{n!}{n^n}\leq \text{per}(A).$$

For stochastic matrices, the product of all entries can be interpreted in terms of Markov chains.

Observation: Suppose that $(X_r)_r$ is an irreducible aperiodic Markov chain with underlying set $\{1,\dots,n\}$ and with transition matrix $A$. Furthermore, suppose that every entry in $B$ is $1/n$.

For almost all tuples $(y_r)_r\in\{1,\dots,r\}^{\omega}$, we have $$\lim_{N\rightarrow\infty}P(X_0=y_0,\dots,X_N=y_N)^{1/N}=\prod_{i,j}a_{i,j}^{n^{-2}}\leq 1/n.$$

If each entry in $A$ is positive, then the spectral radius $\rho(A)$ of $A$ is an eigenvalue of $A$.

The $i,j$-th entry in $A^{N}$ is the sum of all products of the form $a_{i,i_{1}}\dots a_{i_{N-1},j}$. However, the geometric mean value of $a_{i,i_{1}},\dots,a_{i_{N-1},j}$ is about $(\prod_{i,j}a_{i,j})^{1/n^2}$, so the geometric mean value of the product $a_{i,i_{1}}\dots a_{i_{N-1},j}$ is about $(\prod_{i,j}a_{i,j})^{N/n^2}$. And since the $i,j$-th entry is the sum of $n^{N-1}$ many factors, we estimate that the $i,j$-th entry in $A^N$ is about $n^{N-1}(\prod_{i,j}a_{i,j})^{N/n^2}$ which is about $[n\cdot(\prod_{i,j}a_{i,j})^{1/n^2}]^{N}$. Therefore, we have $$n\cdot(\prod_{i,j}a_{i,j})^{1/n^2}\leq\rho(A).$$

By using the arithmetic-geometric mean inequality, if each entry $a_{i,j}$ in $A$ is positive, we can bound several quantities related to $A$ below by the product $\prod_{i,j}a_{i,j}$. The geometric-arithmetic mean inequality states that $(x_1\dots x_n)^{1/n}\leq\frac{1}{n}(x_1+\dots+x_n)$ whenever $x_1,\dots,x_n$ are non-negative. Therefore, $n(x_1\dots x_n)^{1/n}\leq x_1+\dots+x_n$ whenever $x_1,\dots,x_n$ are non-negative.

Suppose $A$ is a matrix with non-negative entries. Then we obtain the following bound for the permanent of $A$:

$$\text{per}(A)=\sum_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)}\geq n!\cdot(\prod_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)})^{1/n!}=n!\cdot\big((\prod_{i,j}a_{i,j})^{(n-1)!}\big)^{1/n!}$$ $$=n!\cdot(\prod_{i,j}a_{i,j})^{1/n}.$$

Here, equality is reached if and only if every entry in $A$ is the same. While this inequality is easy to prove, the Van der Waerden's conjecture is a result that was proven in 1980 that strengthens this inequality whenever $A$ is doubly stochastic.

If $A$ is doubly stochastic, then by again applying the geometric-arithmetric mean inequality, we obtain $\prod_{i,j}a_{i,j}\leq n^{-n^2}.$

Van der Waerden's conjecture states that $$n!\cdot(\prod_{i,j}a_{i,j})^{1/n}\leq\frac{n!}{n^n}\leq \text{per}(A)$$ whenever $A$ is doubly stochastic.

For stochastic matrices, the product of all entries can be interpreted in terms of Markov chains.

Observation: Suppose that $(X_r)_r$ is an irreducible aperiodic Markov chain with underlying set $\{1,\dots,n\}$ and with transition matrix $A$. Furthermore, suppose that every entry in $B$ is $1/n$.

For almost all tuples $(y_r)_r\in\{1,\dots,r\}^{\omega}$, we have $$\lim_{N\rightarrow\infty}P(X_0=y_0,\dots,X_N=y_N)^{1/N}=\prod_{i,j}a_{i,j}^{n^{-2}}\leq 1/n.$$

If each entry in $A$ is positive, then the spectral radius $\rho(A)$ of $A$ is an eigenvalue of $A$.

The $i,j$-th entry in $A^{N}$ is the sum of all products of the form $a_{i,i_{1}}\dots a_{i_{N-1},j}$. However, the geometric mean value of $a_{i,i_{1}},\dots,a_{i_{N-1},j}$ is about $(\prod_{i,j}a_{i,j})^{1/n^2}$, so the geometric mean value of the product $a_{i,i_{1}}\dots a_{i_{N-1},j}$ is about $(\prod_{i,j}a_{i,j})^{N/n^2}$. And since the $i,j$-th entry is the sum of $n^{N-1}$ many factors, we estimate that the $i,j$-th entry in $A^N$ is about $n^{N-1}(\prod_{i,j}a_{i,j})^{N/n^2}$ which is about $[n\cdot(\prod_{i,j}a_{i,j})^{1/n^2}]^{N}$. Therefore, we have $$n\cdot(\prod_{i,j}a_{i,j})^{1/n^2}\leq\rho(A).$$

There is an inequality between the product of all entries of the matrix and the permanent of a matrix with non-negative entries. The geometric-arithmetic mean inequality states that  $(x_1\dots x_n)^{1/n}\leq\frac{1}{n}(x_1+\dots+x_n)$ whenever $x_1,\dots,x_n$ are non-negative. Therefore, $n(x_1\dots x_n)^{1/n}\leq x_1+\dots+x_n$ whenever $x_1,\dots,x_n$ are non-negative.

Suppose $A$ is a matrix with non-negative entries. Then

$$\text{per}(A)=\sum_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)}\geq n!\cdot(\prod_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)})^{1/n!}=n!\cdot\big((\prod_{i,j}a_{i,j})^{(n-1)!}\big)^{1/n!}$$ $$=n!\cdot(\prod_{i,j}a_{i,j})^{1/n}.$$

Here, equality is reached if and only if every entry in $A$ is the same. While this inequality is easy to prove, the Van der Waerden's conjecture is a result that was proven in 1980 that strengthens this inequality.

If $A$ is doubly stochastic, then by again applying the geometric-arithmetric mean inequality, we obtain $\prod_{i,j}a_{i,j}\leq n^{-n^2}.$

Van der Waerden's conjecture states that $$n!\cdot(\prod_{i,j}a_{i,j})^{1/n}\leq\frac{n!}{n^n}\leq \text{per}(A).$$

For stochastic matrices, the product of all entries can be interpreted in terms of Markov chains.

Observation: Suppose that $(X_r)_r$ is an irreducible aperiodic Markov chain with underlying set $\{1,\dots,n\}$ and with transition matrix $A$. Furthermore, suppose that every entry in $B$ is $1/n$.

For almost all tuples $(y_r)_r\in\{1,\dots,r\}^{\omega}$, we have $$\lim_{N\rightarrow\infty}P(X_0=y_0,\dots,X_N=y_N)^{1/N}=\prod_{i,j}a_{i,j}^{n^{-2}}\leq 1/n.$$

By using the arithmetic-geometric mean inequality, if each entry $a_{i,j}$ in $A$ is positive, we can bound several quantities related to $A$ below by the product $\prod_{i,j}a_{i,j}$. The geometric-arithmetic mean inequality states that  $(x_1\dots x_n)^{1/n}\leq\frac{1}{n}(x_1+\dots+x_n)$ whenever $x_1,\dots,x_n$ are non-negative. Therefore, $n(x_1\dots x_n)^{1/n}\leq x_1+\dots+x_n$ whenever $x_1,\dots,x_n$ are non-negative.

Suppose $A$ is a matrix with non-negative entries. Then

$$\text{per}(A)=\sum_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)}\geq n!\cdot(\prod_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)})^{1/n!}=n!\cdot\big((\prod_{i,j}a_{i,j})^{(n-1)!}\big)^{1/n!}$$ $$=n!\cdot(\prod_{i,j}a_{i,j})^{1/n}.$$

Here, equality is reached if and only if every entry in $A$ is the same. While this inequality is easy to prove, the Van der Waerden's conjecture is a result that was proven in 1980 that strengthens this inequality.

If $A$ is doubly stochastic, then by again applying the geometric-arithmetric mean inequality, we obtain $\prod_{i,j}a_{i,j}\leq n^{-n^2}.$

Van der Waerden's conjecture states that $$n!\cdot(\prod_{i,j}a_{i,j})^{1/n}\leq\frac{n!}{n^n}\leq \text{per}(A).$$

For stochastic matrices, the product of all entries can be interpreted in terms of Markov chains.

Observation: Suppose that $(X_r)_r$ is an irreducible aperiodic Markov chain with underlying set $\{1,\dots,n\}$ and with transition matrix $A$. Furthermore, suppose that every entry in $B$ is $1/n$.

For almost all tuples $(y_r)_r\in\{1,\dots,r\}^{\omega}$, we have $$\lim_{N\rightarrow\infty}P(X_0=y_0,\dots,X_N=y_N)^{1/N}=\prod_{i,j}a_{i,j}^{n^{-2}}\leq 1/n.$$

If each entry in $A$ is positive, then the spectral radius $\rho(A)$ of $A$ is an eigenvalue of $A$.

The $i,j$-th entry in $A^{N}$ is the sum of all products of the form $a_{i,i_{1}}\dots a_{i_{N-1},j}$. However, the geometric mean value of $a_{i,i_{1}},\dots,a_{i_{N-1},j}$ is about $(\prod_{i,j}a_{i,j})^{1/n^2}$, so the geometric mean value of the product $a_{i,i_{1}}\dots a_{i_{N-1},j}$ is about $(\prod_{i,j}a_{i,j})^{N/n^2}$. And since the $i,j$-th entry is the sum of $n^{N-1}$ many factors, we estimate that the $i,j$-th entry in $A^N$ is about $n^{N-1}(\prod_{i,j}a_{i,j})^{N/n^2}$ which is about $[n\cdot(\prod_{i,j}a_{i,j})^{1/n^2}]^{N}$. Therefore, we have $$n\cdot(\prod_{i,j}a_{i,j})^{1/n^2}\leq\rho(A).$$

There is at least an inequality between the product of all entries of the matrix and the permanent of a matrix with non-negative entries. The geometric-arithmetic inequality states that $(x_1\dots x_n)^{1/n}\leq\frac{1}{n}(x_1+\dots+x_n)$ whenever $x_1,\dots,x_n$ are non-negative. Therefore, $n(x_1\dots x_n)^{1/n}\leq x_1+\dots+x_n$ whenever $x_1,\dots,x_n$ are non-negative.

Suppose $A$ is a matrix with non-negative entries. Then

$$\text{per}(A)=\sum_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)}\geq n!\cdot(\prod_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)})^{1/n!}=n!\cdot\big((\prod_{i,j}a_{i,j})^{(n-1)!}\big)^{1/n!}$$ $$=n!\cdot(\prod_{i,j}a_{i,j})^{1/n}.$$

Here, equality is reached if and only if every entry in $A$ is the same.

There is an inequality between the product of all entries of the matrix and the permanent of a matrix with non-negative entries. The geometric-arithmetic mean inequality states that $(x_1\dots x_n)^{1/n}\leq\frac{1}{n}(x_1+\dots+x_n)$ whenever $x_1,\dots,x_n$ are non-negative. Therefore, $n(x_1\dots x_n)^{1/n}\leq x_1+\dots+x_n$ whenever $x_1,\dots,x_n$ are non-negative.

Suppose $A$ is a matrix with non-negative entries. Then

$$\text{per}(A)=\sum_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)}\geq n!\cdot(\prod_{\sigma\in S_{n}}\prod_{k=1}^{n}a_{k,\sigma(k)})^{1/n!}=n!\cdot\big((\prod_{i,j}a_{i,j})^{(n-1)!}\big)^{1/n!}$$ $$=n!\cdot(\prod_{i,j}a_{i,j})^{1/n}.$$

Here, equality is reached if and only if every entry in $A$ is the same. While this inequality is easy to prove, the Van der Waerden's conjecture is a result that was proven in 1980 that strengthens this inequality.

If $A$ is doubly stochastic, then by again applying the geometric-arithmetric mean inequality, we obtain $\prod_{i,j}a_{i,j}\leq n^{-n^2}.$

Van der Waerden's conjecture states that $$n!\cdot(\prod_{i,j}a_{i,j})^{1/n}\leq\frac{n!}{n^n}\leq \text{per}(A).$$

For stochastic matrices, the product of all entries can be interpreted in terms of Markov chains.

Observation: Suppose that $(X_r)_r$ is an irreducible aperiodic Markov chain with underlying set $\{1,\dots,n\}$ and with transition matrix $A$. Furthermore, suppose that every entry in $B$ is $1/n$.

For almost all tuples $(y_r)_r\in\{1,\dots,r\}^{\omega}$, we have $$\lim_{N\rightarrow\infty}P(X_0=y_0,\dots,X_N=y_N)^{1/N}=\prod_{i,j}a_{i,j}^{n^{-2}}\leq 1/n.$$