On permutation

For any permutation \sigma:\{1,2,\dots,n\}\to\{1,2,\dots,n\} define its displacement  as

\displaystyle D(\sigma)=\prod_{i=1}^n |i-\sigma(i)|

What is greater: the sum of displacements of even permutations or the sum of displacements of odd permutations? The answer may depend on n.


The sum of D(\sigma) over the even permutations minus the one over the odd permutations is the determinant of the matrix A with entries a_{i,j}=\vert i-j\vert and this determinant is known to be

\det A = (-1)^{n-1} (n-1) 2^{n-2}

Read more

Equal determinants

Let  A, B \in \mathbb{R}^{n \times n} that are diagonizable in  \mathbb{R} . If  \det (A^2+B^2)=0 and  AB=BA   then prove that

 \det A = \det B =0


The key point here is that the matrices are simultaneously diagonisable. Thus , there exists an invertible matrix C\in\mathbb{M}_{n}(\mathbb{R}) and diagonisable matrices P\,,Q\in\mathbb{M}_{n}(\mathbb{R}) such that



    \begin{align*} 0&=\det(A^2+B^2)\\&=\det(C\,P^2\,C^{-1}+C\,Q^2\,C^{-1})\\ &=\det(C\,(P^2+Q^2)\,C^{-1})\\ &=\det(P^2+Q^2)\\ &=\prod_{i=1}^{n}\left(p_{i}^2+q_{i}^2\right) \quad (1) \end{align*}

where p_{i}\,,1\leq i\leq n are the diagonial elements of P and q_{i}\,,1\leq i\leq n of Q. According to (1) we have that

p_{i}^2+q_{i}^2=0 \quad \text{for some} \; i\in\left\{1,...,n\right\}

But p_{i}\,,q_{i}\in\mathbb{R}, so p_{i}=q_{i}=0 and finally we conclude that:

\displaystyle \det(A)=\det (P)=\prod_{i=1}^{n}p_{i}=0=\prod_{i=1}^{n}q_{i}=\det(Q)=\det(B)

Read more

Hadamard Inequality

Let \mathbf{a_1, a_2, \dots, a_N} be column vectors in \mathbb{R}^N and let A=(a_1, a_2, \dots, a_N) be the corresponding N \times N real matrix. Then the following inequality holds:

(1)   \begin{equation*} \left | \det A \right |\leq \prod_{n=1}^{N}\left \| a_n \right \| \end{equation*}

where \left \| \cdot \right \| is the Euclidean norm on vectors in \mathbb{R}^N. In continuity , give the geometrical interpretation of the inequality above.


By the Gramm – Schmidt process we can establish the existence of an orthonormal basis \mathbf{b_1, b_2, \dots, b_N}$ for $\mathbb{R}^N such that

(2)   \begin{equation*} {\rm span}_{\mathbb{R}} \left \{ \mathbf{a_1, a_2, \dots, a_N} \right \}={\rm span}_{\mathbb{R}}\left \{ \mathbf{a_1, a_2, \dots, b_N} \right \} \end{equation*}

for each n=1, 2, \dots, N. Now, we may write B=(\mathbf{b_1, b_2, \dots, b_N}) for the corresponding N \times N real and orthogonal matrix. By orthogonality each vector \xi in \mathbb{R}^N has an expansion as:

\displaystyle \xi = \sum_{n=1}^{N}\langle \xi, \mathbf{b}_n\rangle \mathbf{b}_n \Rightarrow \left \| \xi \right \|^2 = \sum_{n=1}^{N}\left | \langle \xi, \mathbf{b}_n \rangle \right |^2

On the other hand (2) implies that each vector \mathbf{a}_m has a shorter expansion of the form:

(3)   \begin{equation*} \mathbf{a}_m = \sum_{n=1}^{m}\langle \mathbf{a}_m, \mathbf{b}_n \rangle \mathbf{b}_n \end{equation*}

Alternatively let C=(c_{k\ell}) be the N \times N upper triangular matrix defined as:

\displaystyle c_{k\ell}= \langle \mathbf{a}_\ell, \mathbf{b}_k \rangle \;\; \text{if} \; 1 \leq k \leq \ell \;\; \textbf{and} \;\; c_{k \ell}=0 \; \; \text{if} \; \ell < k \leq N

Then (3) is restated as A=BC and using again the fact that B has orthonormal columns and the fact that C is upper triangular we get:

    \begin{align*} \left ( \det A \right )^2 &=\det \left ( A^T A \right ) \\ &= \det \left ( C^T B^T BC \right )\\ &= \det \left ( C^T C \right )\\ &= \left ( \det C \right )^2 \\ &= \prod_{n=1}^{N}\left | \langle \mathbf{a}_n , \mathbf{b}_n \rangle \right |^2 \\ &\leq \prod_{n=1}^{N} \left ( \sum_{m=1}^{n}\left | \langle \mathbf{a}_n, \mathbf{b}_n \rangle \right |^2 \right ) \\ &=\prod_{n=1}^{N} \left \| \mathbf{a}_n \right \|^2 \end{align*}


  • The above argument also shows that there exists equality if and only if

    \displaystyle \left | \langle \mathbf{a}_n, \mathbf{b}_n \rangle \right |^2 = \sum_{m=1}^{n}\left | \langle \mathbf{a}_m , \mathbf{b}_n \rangle \right |^2

    for each n. That is , if and only if, \mathbf{a}_n= \langle \mathbf{a}_n, \mathbf{b}_n \rangle \mathbf{b}_n. This can only be achieved if the vectors \mathbf{a}_n are pairwise orthogonal.

  • The geometrical interpretation of this inequality is the following: The volume of an n dimensional parallelepiped produced by n vectors can not exceed the product of their measures.

Read more

No rational function

Prove that there exists no rational function such that

\displaystyle f(n)=1+ \frac{1}{2} + \cdots + \frac{1}{n} \quad \text{forall} \; n \in \mathbb{N}


Suppose , on the contrary , that such function exists. Since the harmonic series diverges we conclude that the limit of our function in infinity is infinity. This, in return means that the degree of the nominator , call that m is greater that the one of the denominator , call that n. Extracting x^{n-m} in the nominator we get that

\displaystyle R(x)=\frac{P(x)}{Q(x)} = x^{m-n} s(x)

The limit of s at infinity is finite and call that \ell. Hence:

\begin{aligned} \lim_{x \rightarrow +\infty} \left ( \frac{f(x)}{g(x)} - \ln x \right ) &= \lim_{x \rightarrow +\infty} \left [ x^{m-n} s(x) - \ln x \right ] \\ &= \lim_{n \rightarrow +\infty} x^{m-n} \left [ s(x) - \frac{\ln x}{x^{m-n}} \right ]\\ &= +\infty \end{aligned}

and of course this contradicts the fact that

\displaystyle \lim \left ( \mathcal{H}_n - \ln n \right ) = \gamma

where \gamma is the Euler  – Mascheroni constant .

Read more

Non existence of sequence of continuous functions

Prove that there does not exist a sequence of continuous functions f_n:[0, 1] \rightarrow \mathbb{R} such that converges pointwise, to the function \chi_{\mathbb{Q}} , where \chi_{\mathbb{Q}} is the characteristic polynomial of the rationals in [0, 1].


The indicator of the rationals is no other function than

\chi_{\mathbb{Q}}= \left\{\begin{matrix} 1& ,& x \in \mathbb{Q}\\ 0& , & \text{elsewhere} \end{matrix}\right.

It is known that pointwise limits of continuous functions have a meagre set of points of continuity. However, this function is discontinuous everywhere and thus we cannot expect a sequence of continuous functions to converge pointwise to it.

Read more