Search This Blog

Sufficient conditions for integrability

This post is about single variable functions $f : [a, b] \to \mathbb{R}$ defined in a finite closed interval, and about some sufficient conditions for their integrability in the interval $[a, b]$. Here $a$ and $b$ are real numbers of course.

Integrability refers to the existence of the definite integral 

$$\int\limits_a^b f(x)\,dx$$

One should note that there are different definitions of integrability (i.e. different definitions of the definite integral shown above).

The one I am referring to here is Darboux integrability. This one is equivalent to Riemann integrability. 

Then there is also Lebesgue integrability which allows a wider family of functions to be classified as integrable. So all functions which are Darboux/Riemann integrable are also Lebesgue integrable but the converse is not true. This is a very interesting topic and relates to measure theory.

OK... so here are several sufficient conditions for Darboux/Riemann integrability. 

Theorem 1: If the function $f : [a, b] \to \mathbb{R}$ is defined and continuous in the finite closed interval $[a,b]$, it is integrable in $[a,b]$. 

Theorem 2: If the function $f : [a, b] \to \mathbb{R}$ is defined and bounded in the finite closed interval $[a,b]$, and if it is discontinuous only at a finite number of points, then it is integrable in $[a,b]$. 

Theorem 3: If the function $f : [a, b] \to \mathbb{R}$ is defined and monotonic in the finite closed interval $[a,b]$, then it is integrable in $[a,b]$.

Note that the last theorem does not disallow a situation where $f$ has infinitely many points of discontinuity. That situation is allowed and the function if still integrable (provided that it's monotonic, as the theorem says).

Again, it should be pointed out that these are just sufficient conditions for integrability, they are not necessary. There are functions which do not satisfy the conditions of any of these three theorems but are still integrable. 


Algebra Notes 1

1.1) Fundamental theorem of algebra (D'Alembert)

Every non-zero, single-variable, degree $n$ polynomial with complex coefficients has, counted with multiplicity, exactly $n$ complex roots. 

For more details see here

1.2) Number field definition (A):

Let $F$ be a subset of $\mathbb{C}$ which contains at least two elements. We say that $F$ is a number field if the following conditions are met: 

a) if $z_1$ and $z_2$ are arbitrary numbers from $F$, then the numbers $z_1 + z_2$, $z_1 - z_2$, $z_1 \cdot z_2$ are also in $F$, 

b) if $z_1$ and $z_2$ are arbitrary numbers from $F$ and $z_2 \ne 0$, then $z_1 / z_2$ is also in $F$. 

1.3) Number field definition (B):

Let $F$ be a subset of $\mathbb{C}$ which contains at least two elements. We say that $F$ is a number field if the following conditions are met: 

a) if $z_1$ and $z_2$ are arbitrary numbers from $F$, then the numbers $z_1 + z_2$, $z_1 - z_2$, $z_1 \cdot z_2$ are also from $F$; 

b) if $z \in F$ and $z \ne 0$, then $z^{-1} \in F$ 

1.4) Note: Not all fields in mathematics are considered number fields (e.g. finite Galois fields are not considered number fields). The number sets $\mathbb{Q}, \mathbb{R}, \mathbb{C}$ (equipped with the usual algebraic operations) are number fields. The number sets $\mathbb{N}, \mathbb{Z}$ are not number fields.

1.5) Theorem: Every number field is a superset of the field of the rational numbers $\mathbb{Q}$.

1.6) Notations: 

a) $F_{m \times n}$ - the set of all $m \times n$ matrices with elements from the number field $F$

b) $M_{n}(F)$ - the set of all $n \times n$ square matrices with elements from the number field $F$; these are also called square matrices of order $n$ 

c) If $A = (a_{ij})_{m\times n}$ is a matrix, then by $A^t$ we denote the transposed matrix of the matrix $A$; it is defined as follows: $A^t = (a_{ji})_{n\times m}$ 

d) $E_n$ or just $E$ is the identity matrix ($E_n$ just emphasizes the fact that the order of the matrix is $n$)

e) $E_{ij}$ is the matrix from $F_{m \times n}$ which has element $1$ at position $(i,j)$ and zero elements at all other positions $(k,l) \ne (i,j)$

1.7) Operations on matrices:

a) sum of matrices: $A+B$

b) multiplication of a matrix with a number: $\lambda A$

c) transposed matrix: $A^t$

1.8) Property:

Obviously if $A = (a_{ij})_{m\times n}$ is an arbitrary matrix from $F_{m \times n}$ then $$A = \sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij} \cdot E_{ij}$$

1.9) Definition:  

a) The matrices which have a single row (or a single column) are called row matrices (or column matrices), or n-tuples, or also n-dimensional vectors.

b) The set of all n-tuples with elements from the number field $F$ is denoted by $F^n$ 

c) The n-tuples  

$e_1 = (1, 0, 0, \dots, 0, 0),\ e_2 = (0, 1, 0, \dots, 0, 0),\ e_3 = (0, 0, 1, \dots, 0, 0),\ \dots\ ,\ $ 

$e_{n-1} = (0, 0, 0, \dots, 1, 0),\ e_{n} = (0, 0, 0, \dots, 0, 1)$ 

are called unit vectors or unit n-dimensional vectors.

1.10) Note: If $a = (a_1, a_2, \dots, a_n) \in F^n$ then obviously $a = a_1 e_1 + a_2 e_2 + \dots + a_n e_n$ This expression for $a$ is called a linear combination. In this particular case, $a$ is linear combination of the unit vectors $e_1, e_2, \dots, e_n$ 

1.11) Properties of the transposed matrix:

a) $(A^t)^t = A$ 

b) $(A+B)^t = A^t + B^t$ 

c) $(\lambda A)^t = \lambda A^t$ (for any $\lambda \in F$)


A nice symmetric system of linear equations

Suppose we want to solve the following system of linear equations in which $a$ and $b_i$ are real parameters. 

$$ax_1 + ax_2 + \dots + ax_{n-1} + (a+1)x_n = b_1$$
$$ax_1 + ax_2 + \dots + (a+1)x_{n-1} + ax_n = b_2$$
$$\dots$$
$$(a+1)x_1 + ax_2 + \dots + ax_{n-1} + ax_n = b_n$$

We can proceed as follows.

Denote 

$$T = \sum_{i=1}^n b_i$$
$$S = \sum_{i=1}^n x_i$$

Then the given system of equations can be rewritten as 

$$aS + x_n = b_1$$
$$aS + x_{n-1} = b_2$$
$$\dots$$
$$aS + x_2 = b_{n-1}$$
$$aS + x_1 = b_n$$

Then it follows that 

$$x_1 - b_n = x_n - b_1$$
$$x_2 - b_{n-1} = x_n - b_1$$
$$\dots$$
$$x_{n-1} - b_2 = x_n - b_1$$
$$x_n - b_1 = x_n - b_1$$

Let's call these equations the differences equations

When we sum up these equations we get that  

$S-T = nx_n - nb_1$

So it follows that 

$aS-aT = anx_n - anb_1$
$(b_1 - x_n)-aT = anx_n - anb_1$
$b_1(1 + an)-aT = (1 + an)x_n$

Note that in this equation only $x_n$ is unknown. Also, we can get analogical equations for all unknowns $x_i$ ($i=1,2,\dots,n)$. They look like this   

$$(1 + an)b_{n+1-i}-aT = (1 + an)x_i \tag{*}$$

We note here that the equations $(*)$ (for $i=1,2,\dots,n$) are just a subsequence of the original system. They are not necessarily equivalent to the original system. 

Now based on $(*)$ we can look at the possible cases for the parameters $a$ and $b_i$ (where $i=1,2,\dots,n$). 

Case (1) 

$1+an \ne 0$ i.e. $a \ne -1/n$ 

In this case from $(*)$ we find that 

$$x_1 = b_{n} - \frac{aT}{1+an}$$
$$x_2 = b_{n-1} - \frac{aT}{1+an}$$
$$\dots$$
$$x_n = b_{1} - \frac{aT}{1+an}$$

A direct check (substituting the $x_i$ unknowns in the original system with these values) shows that these values are indeed a solution. So in this case the original system has a unique solution given by the formulas above.

Case (2) 
$1+an = 0$ i.e. $a = -1/n$ and $aT \ne 0$
Note that since $a=-1/n$ the condition $aT \ne 0$ is in fact equivalent to $T \ne 0$. 
So this case is the case when $a=-1/n$ and $T \ne 0$.

Obviously the equations $(*)$ cannot be satisfied in this case.  
So in this case the system has no solutions. 

Case (3) 
$1+an = 0$ i.e. $a = -1/n$ and $aT = 0$
Note that since $a=-1/n$ the condition $aT = 0$ is in fact equivalent to $T=0$.  
So this case is the case when $a=-1/n$ and $T = 0$.

Now $(*)$ is always satisfied. Going back to the differences equations we see that if we let $x_n=p$ we get 

$$x_1 = p - b_1 + b_n$$
$$x_2 = p - b_1 + b_{n-1}$$
$$\dots$$
$$x_{n-1} = p - b_1 + b_2$$
$$x_{n} = p$$

Again, a direct check (substituting the $x_i$ unknowns in the original system with these values) shows that these values are indeed a solution. So in this case the system has infinite number of solutions which depend on a single parameter $x_n = p$. 

No other cases are possible logically. So this completes the solution of the given system of linear equations.

An application of the rational root theorem

This problem is a nice application of the rational root theorem so I present it here together with a solution which I was able to construct.

Problem: Let $f(x) = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$ be a polynomial with integer coefficients ($a_i \in \mathbb{Z}$). Here $n \ge 0, n \in \mathbb{Z}$. The number $\alpha = \frac{p}{q}$ is a rational root of $f(x)$, where $p \in \mathbb{Z}$, $q \in \mathbb{Z}$, $q \ne 0$, $(p,q) = 1$. Prove that $(mq-p)\ |\ f(m)$ for every number $m \in \mathbb{Z}$ such that $(mq-p) \ne 0$.

Solution: We will apply induction on the degree $n$ of $f(x)$.

1) Let $n=0$ i.e. $f(x) = a_0$ is a constant polynomial. Since the number $\alpha$ is a root, it follows that $a_0=0$ i.e. $f(x)$ is the constant $0$. But then $f(m)=0$ for every $m \in \mathbb{Z}$. So for each integer $m$ such that $(mq-p) \ne 0$ we trivially obtain that $(mq-p)\ |\ f(m)$. Thus we proved the statement in the case when $n=0$.

2) Let's also prove the statement when $n=1$. In this case $f(x) = a_0x + a_1$ and $a_0 \ne 0$. From the rational root theorem we get that $q\ |\ a_0$. Then $a_0 = q c_0$ where $c_0 \in \mathbb{Z}$. So $f(x) = c_0 q x + a_1$. Since $\frac{p}{q}$ is a root of $f(x)$ we get $c_0 q (p/q) + a_1 = 0$ which gives us that $c_0 p + a_1 = 0$. Now for $f(x)$ we get the following $f(x) = c_0qx + a_1 = c_0 (qx-p) + (c_0p + a_1)$. But as we saw $(c_0p + a_1) = 0$. So finally $f(x) = c_0 (qx-p) = c_0 (xq - p)$. From this expression we see that $f(m) = c_0 (mq-p)$ for every integer $m$. Then if $m$ is an integer such that $(mq-p) \ne 0$ we obviously get that $(mq-p)\ |\ f(m)$ which is what we wanted to prove.

3) Induction hypothesis. We now assume the statement is true for all polynomials $g(x)$ which satisfy the conditions of the problem statement, and have degrees $\le (n-1)$. Again, the statement is as follows: $(mq-p)\ |\ g(m)$ for every number $m \in \mathbb{Z}$ such that $(mq-p) \ne 0$

4) Now let $f(x) = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$ be a polynomial of degree $n$ (where $n \ge 2$) which satisfies all conditions of the problem statement. Again from the rational root theorem we obtain that $q\ |\ a_0$ so we can write $a_0 = q c_0$, where $c_0 \in \mathbb{Z}$. Then 

$f(x) = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n = $ 

$ = q c_0 x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n = $

$ = c_0(xq - p) x^{n-1} + (a_1 + c_0p)x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$ 

So if we denote $h(x) = (a_1 + c_0p)x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$ we obtain that 

$f(x) = c_0(xq - p) x^{n-1} + h(x) \tag{*}$ 

Now we know $p/q$ is a root of $f(x)$. But obviously it's also a root of $c_0(xq - p) x^{n-1}$. So from equality $(*)$ it follows that $p/q$ is also a root of $h(x)$. This means that now $h(x)$ satisfies all the conditions of the problem statement (it has integer coefficients, $p/q$ is its root etc.). Also $h(x)$ has a degree which does not exceed $n-1$. So we can apply to it the induction hypothesis and when we do so, we get that $(mq-p)\ |\ h(m)$ for every integer $m$ such that $(mq - p) \ne 0$. Obviously it's also true that $(mq-p)\ |\ c_0(mq - p) m^{n-1}$ for every integer $m$ such that $(mq - p) \ne 0$. From the last two statements we obtain that $(mq-p)\ |\ (c_0(mq - p) m^{n-1} + h(m))$ for every integer $m$ such that $(mq - p) \ne 0$. But from $(*)$ this expression $(c_0(mq - p) m^{n-1} + h(m))$ is equal to $f(m)$. Thus we obtain that $(mq-p)\ |\ f(m)$ for every integer $m$ such that $(mq - p) \ne 0$. This completes the induction and therefore the statement is now completely proved.

Note 1: In the special case when $m = 1$ we get that $(p-q)\ |\ f(1)$ (unless $q = p = 1$ of course)

Note 2: In the special case when $m = -1$ we get that $(p+q)\ |\ f(-1)$ (unless $q = -p = \pm1$ of course)


A problem about scalar matrices $A = \lambda \cdot E$

I encountered this problem on MathSE 

Even though this question was heavily downvoted, I think it's quite a nice problem. Here it is. 

We are given that $A$ is a square $n \times n$ matrix which commutes with all invertible matrices of the same size $n$.  

Prove that $A$ is the scalar matrix i.e. $A = \lambda E\ $ where $E$ is the identity matrix and $\lambda$ is a scalar/number. 

Let's solve this problem for the case $n=3$. Solving for any $n$ is fully analogical to the case $n=3$.

Let's assume 

$$A = \begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}$$

and let's assume it commutes with all invertible matrices of size 3.

Let's pick the matrix 

$$B = \begin{bmatrix}1&0&0\\0&2&0\\0&0&3\end{bmatrix}$$

This one is obviously invertible as its determinant is equal to $6 = 3!$

Now we use the fact that $AB=BA$.

$$AB = \begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix} \cdot \begin{bmatrix}1&0&0\\0&2&0\\0&0&3\end{bmatrix} = \begin{bmatrix}a_{11}&2a_{12}&3a_{13}\\a_{21}&2a_{22}&3a_{23}\\a_{31}&2a_{32}&3a_{33}\end{bmatrix}$$


$$BA = \begin{bmatrix}1&0&0\\0&2&0\\0&0&3\end{bmatrix} \cdot \begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix} = \begin{bmatrix}a_{11}&a_{12}&a_{13}\\2a_{21}&2a_{22}&2a_{23}\\3a_{31}&3a_{32}&3a_{33}\end{bmatrix}$$

But these two resulting matrices must be equal. Comparing their respective elements, it's easy to see that we get the following. $$a_{ij} = 0,\ \ for\ \ all\ \ i \ne j \tag{1}$$

OK... So now our matrix $A$ gets the form

$$A = \begin{bmatrix}a&0&0\\0&b&0\\0&0&c\end{bmatrix} \tag{2}$$

Now let's pick another matrix $C$ and use the fact that $A$ commutes with $C$. We pick $C$ to be e.g. the Vandermonde matrix for the numbers 1,2,3 (the important part is to pick the alphas in the Vandermonde matrix to be all distinct numbers).

$$C = \begin{bmatrix}1^0&1^1&1^2\\2^0&2^1&2^2\\3^0&3^1&3^2\end{bmatrix}$$

We know that the determinant of $C$ equals $(2-1)(3-1)(3-2) = 2 \ne 0$ so $C$ is invertible.

Now in a similar way we use that $A$ commutes with $C$ i.e. $AC = CA$.

$$AC = \begin{bmatrix}a&0&0\\0&b&0\\0&0&c\end{bmatrix} \cdot \begin{bmatrix}1^0&1^1&1^2\\2^0&2^1&2^2\\3^0&3^1&3^2\end{bmatrix} = \begin{bmatrix}a&a&a\\b&2b&4b\\c&3c&9c\end{bmatrix}$$ 

$$CA =  \begin{bmatrix}1^0&1^1&1^2\\2^0&2^1&2^2\\3^0&3^1&3^2\end{bmatrix} \cdot \begin{bmatrix}a&0&0\\0&b&0\\0&0&c\end{bmatrix} = \begin{bmatrix}a&b&c\\a&2b&4c\\a&3b&9c\end{bmatrix}$$ 

But these two resulting matrices must be equal. Comparing their first columns we finally get that $a=b=c$.

Thus our matrix $A$ finally gets the form

$$A = \begin{bmatrix}a&0&0\\0&a&0\\0&0&a\end{bmatrix} \tag{3}$$

which is exactly what we wanted to prove.


Computing the determinant of a Vandermonde-like matrix

This is a problem from a students competition but it looks quite straightforward to solve.

The task is to compute the determinant of the following matrix.

$$A = \begin{bmatrix}1&2&3&...&n\\1^2&2^2&3^2&...&n^2\\...&...&...&...&...\\1^n&2^n&3^n&...&n^n\end{bmatrix}$$

What I noticed is that it looks similar to Vandermonde's matrix even though it's not quite that. 

Let's pull out from its determinant a common multiple $k$ from the $k$-th column for each $k=1,2,3,...,n$.

We get 

$$det(A) = n! \cdot \begin{vmatrix}1^0&2^0&3^0&...&n^0\\1^1&2^1&3^1&...&n^1\\...&...&...&...&...\\1^{n-1}&2^{n-1}&3^{n-1}&...&n^{n-1}\end{vmatrix}$$

The matrix whose determinant we got in the RHS of the last equality is the transpose of the Vandermonde matrix (with $\alpha_s = s$, for $s = 1,2,...,n$). Hence its determinant equals the determinant of the Vandermonde matrix itself (since we know that $det(A) = det(A^T)$).

So (leaving aside the $n!$ multiplier) the determinant we are left with now is Vandermonde's determinant for the numbers $1,2,3,...,n$. We know its value is equal to 

$$\prod\limits_{1 \le i \lt j \le n} (j-i)$$

So the result we get now is 

$$det(A) = n! \cdot \prod\limits_{1 \le i \lt j \le n} (j-i)$$

This is the same as 

$$n! \cdot (n-1)^1 \cdot (n-2)^2 \cdot (n-3)^3\ ...\ 3^{n-3} \cdot 2^{n-2} \cdot 1^{n-1}$$

Finally it is not difficult to realize that this expression is equal to 

$$n!\ \cdot (n-1)!\ \cdot (n-2)!\ ... \ 3! \cdot\ 2! \cdot\ 1!$$

So this is our final answer here for the determinant of $A$.


Solving systems of linear equations with SymPy

SymPy is a great Python library for symbolic computation. It can be used e.g. for solving systems of linear equations. So if you are manually solving problems from a linear algebra book, and you want to verify your solutions, you can check them against the solutions that SymPy provides. You just need to know how to code the linear system for SymPy.

Here is an example which illustrates this very well.

import sympy as sp

x, y, z, t = sp.symbols(['x', 'y', 'z', 't'])

solution = solve(

      [

          2 * x + 3 * y -  5*z + 1 * t  -  2  , 

          2 * x + 3 * y -  1*z + 3 * t  -  8  , 

          6 * x + 9 * y -  7*z + 7 * t  - 18  , 

          4 * x + 6 * y - 12*z + 1 * t  -  1   

      ]

      , 

      [x,y,z,t]

)

print(solution)


The code above solves the following system.

$$\begin{bmatrix}2 & 3 & -5 & 1 \\2 & 3 & -1 & 3 \\6 & 9 & -7 & 7 \\4 & 6 & -12 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ t \end{bmatrix} = \begin{bmatrix} 2 \\ 8 \\ 18 \\ 1 \end{bmatrix} $$

The solution which SymPy provides is this one 

{z: 3/2 - t/2, x: -7*t/4 - 3*y/2 + 19/4}

The form of this solution implies that $y$ and $t$ are free variables, and can thus be given any values (i.e. they can be taken as free parameters e.g. $y=a, t=b$). The system is then solved (in terms of $a,b$) for the leading variables which happen to be $x$ and $z$.


Solving the integrals $\int \frac{ \alpha\sin{x} + \beta\cos{x} }{a\sin{x} + b\cos{x}} dx$

I found this as a problem in a book, I solved it, and I kind of liked it. 

So I am going to share the end result here.

The solution to the integral 

$$\int \frac{ \alpha\sin{x} + \beta\cos{x} }{a\sin{x} + b\cos{x}} dx$$ 

is the antiderivative function 

$$F(x) = Ax + B \ln{\left|a\sin{x} + b\cos{x}\right|}$$  

where 

$$A = \frac{\alpha a + \beta b}{a^2+b^2}$$

$$B = \frac{\beta a - \alpha b}{a^2+b^2}$$

One can verify this by differentiating $F(x)$.

The original problem, the one which I encountered was actually asking to find the constants $A$ and $B$.