Meaning of function or mapping or transformation in brief words

DEFINITION:

Given two sets X and Y, a transformation (also called a function or mapping) $f: X \rightarrow Y$ of X into Y is a triple $(X,Y,G)$ where G itself is a collection of ordered pairs $(x,y)$ , the first element of each pair being an element of X, and the second an element of Y, with the condition that each element of X appears as the first element of exactly one pair of G.

If each element of Y appears as the second element of some pair in G, then the transformation is said to be onto.

If each element of Y which appears at all, appears as the second element of exactly one pair in G, then f is said to be one-to-one. Note that a transformation can be onto without being one-to-one and conversely.

As an aid in understanding the above definition, consider the equation $y=x^{2}$ where x is a real number. We may take X to be the set of all real numbers and then the collection G is the set of pairs of $(x,x^{2})$ . Taking Y to be just the set of nonnegative reals will cause f to be onto. But if Y is all real numbers, or all reals greater than -7, or any other set containing the nonnegative reals as a proper subset, the transformation is not onto. With each new choice of Y, we change the triple and hence the transformation.

Continuing with the same example, we could assume that X is the set of nonnegative reals also. Then the transformation is one-to-one, as is easily seen. Depending upon the the choice of Y, the transformation may or may not be onto, of course. Thus, we see that we have stated explicitly the conditions usually left implicit in defining a function in analysis. The reader will find that the seemingly pedantic distinctions made here are really quite necessary.

If $f: X \rightarrow Y$ is a transformation of X into Y, and x is an element of the set X, then we let $f(x)$ denote the second element of the pair in G whose first element is x. That is, $f(x)$ is the “functional value” in Y of the point x. Similarly, if Z is a subset of X, then $f(Z)$ denotes that subset of Y composed of all points $f(z)$ , where z is a point in Z. If y is a point of Y, then by $f^{-1}(y)$ is meant the set of all points in X for which $f(x)=y$ ; and if W is a subset of Y, then $f^{-1}(W)$ is the set theoretic union of the sets $f^{-1}(w)$, where w is in W. Note that $f^{-1}$ can be used as a symbol to denote the triple $(X,Y,G^{'})$ wjere $G^{'}$ consists of all pairs $(y,x)$ that are reversals of pairs in G. But $f^{-1}$ is a transformation only if f is both one-to-one and onto. If A is a subset of X and if $f: X \rightarrow Y$ , then f may be restricted to A to yield a transformation denoted by $f|A: A \rightarrow Y$ , and called the restriction of f to A.

Cheers,

Nalin Pithwa

III. Tutorial problems. Symmetric and alternating functions. RMO and IITJEE math

Posted by Nalin Pithwa

Simplify: $(b^{-1}+c^{1})(b+c-a)+(c^{-1}+a^{-1})(c+a-b)+(a^{-1}+b^{-1})(a+b=c)$
Simplify: $\frac{(x-b)(x-c)}{(a-b)(a-c)} + \frac{(x-c)(x-a)}{(b-c)(b-a)} + \frac{(x-a)(x-b)}{(c-a)(c-b)}$
Simplify: $\frac{b^{2}+c^{2}-a^{2}}{(a-b)(a-c)} + \frac{c^{2}+a^{2}-b^{2}}{(b-c)(b-a)} + \frac{a^{2}+b^{2}-c^{2}}{(c-a)(c-b)}$
Simplify: $\frac{b-c}{1+bc} + \frac{c-a}{1+ca} + \frac{a-b}{1+ab}$
Simplify: $\frac{a(b-c)}{1+bc} + \frac{b(c-a)}{1+ca} + \frac{c(a-b)}{1+ab}$
Factorize: $(b-c)^{2}(b+c-2a)+(c-a)^{2}(c+a-2b)+(a-b)^{2}(a+b-2c)$ . Put $b-c=x, c-a=y, a-b=z$ and $b+c-2a=y-z$
Factorize: $8(a+b+c)^{2}-(b+c)^{2}-(c+a)^{2}-(a+b)^{2}$ . Put $b+c=x, c+a=y, a+b=z$ .
Factorize: $(a+b+c)^{2}-(b+c-a)^{2}-(c+a-b)^{2}+(a+b-c)^{2}$
Factorize: $(1-a^{2})(1-b^{2})(1-c^{2})+(a-bc)(b-ac)(c-ab)$
Express the following substitutions as the product of transpositions: (i) $\left(\begin{array}{cccccc}123456\\654321\end{array}\right)$ (ii) $\left(\begin{array}{cccccc}123456\\246135\end{array}\right)$ (iii) $\left(\begin{array}{cccccc}123456\\641235\end{array}\right)$

Regards,

Nalin Pithwa.

Tutorial problems. I. Symmetric and Alternating functions. RMO/IITJEE Math

Posted by Nalin Pithwa

Exercises:

Show that $(bc-ad)(ca-bd)(ab-cd)$ is symmetric with respect to a, b, c, d.
Show that the following expressions are cyclic with respect to a, b, c, d, taken in this order: $(a-b+c-d)^{2}$ and $(a-b)(c-d)+(b-c)(d-a)$
Expand the expression using $\Sigma$ notation: $(y+z-2x)(z+x-2y)(x+y-2z)$
Expand the expression using $\Sigma$ notation: $(x+y+z)^{2}+(y+z-x)^{2}+(z+x-y)^{2}+(x+y-z)^{2}$
Prove that $(\beta^{2}\gamma^{2}+\gamma^{2}\alpha^{2}+\alpha^{2}\beta^{2})(\alpha+\beta+\gamma)= \Sigma\alpha^{2}\beta^{2}+\alpha\beta\gamma\Sigma\alpha\beta$
Prove that $(\alpha-\beta)(\alpha-\gamma)+(\beta-\gamma)(\beta-\alpha)+(\gamma-\alpha)(\gamma-\beta)=\Sigma{\alpha^{2}}-\Sigma{\alpha}{\beta}$
Prove that $(\beta-\gamma)(\beta+\gamma-\alpha)+(\gamma-\alpha)(\gamma+\alpha-\beta)+(\alpha-\beta)(\alpha+\beta-\gamma)=0$
Prove that : $\alpha(\beta-\gamma)^{2}+\beta(\gamma-\alpha)^{2}+\gamma(\alpha-\beta)^{2}=\Sigma{\alpha^{2}}{\beta}-6\alpha\beta\gamma$
Prove that: $(\beta^{2}\gamma+\beta\gamma^{2}+\gamma^{2}\alpha+\gamma\alpha^{2}+\alpha^{2}\beta+\alpha\beta^{2})(\alpha+\beta+\gamma)=\Sigma{\alpha^{2}}\beta+2\Sigma{\alpha^{2}}{\beta^{2}}+2\alpha\beta\gamma\Sigma{\alpha}$
Prove that : $a^{2}(b+c)+b^{2}(c+a)+c^{2}(a+b)+abc(a+b+c)=\Sigma{a^{2}}.\Sigma{ab}$ .
Prove that: $(a+b-c)(a^{2}+b^{2}-c^{2})+(b+c-a)(b^{2}+c^{2}-a^{2})+(c+a-b)(c^{2}+a^{2}-b^{2})=3\Sigma{a^{3}}-\Sigma{a^{2}{b}}$
Prove that: $(a^{2}+b^{2}+c^{2})(x^{2}+y^{2}+z^{2})=(ax+by+cz)^{2}+(bz-cy)^{2}+(cx-az)^{2}+(ay-bz)^{2}$
Prove that: $(b^{2}-ac)(c^{2}-ab)+(c^{2}-ab)(a^{2}-bc)+(a^{2}-bc)(b^{2}-ac)=-(bc+ca+ab)(a^{2}+b^{2}+c^{2}-bc-ca-ab)$
Prove that: $(a^{2}-bc)(b^{2}-ac)(c^{2}-ab)=abc(a^{2}+b^{2}+c^{2})-(b^{2}c^{2}+c^{2}a^{2}+a^{2}b^{2})$
If one of the numbers a, b, and c is the geometric mean of the other two, use the previous problem to prove the following: $abc(a^{2}+b^{2}+c^{2})=b^{2}c^{2}+c^{2}a^{2}+a^{2}b^{2}$
If the numbers x, y, z taken in some order or other form an AP, use problem 3 to prove that $2(x+y+z)^{2}+27xyz=9(x+y+z)(yz+zx+xy)$
Express $2(a-b)(a-c)+2(b-c)(b-a)+2(c-a)(c-b)$ as the sum of three squares. Hence, show that $(b-c)(c-a)+(c-a)(a-b)+(a-b)(b-c)$ is negative for all real values of a, b, c except when $a=b=c$ . Hint: Put $b-c=x$ , $c-a=y$ , $a-b=z$ , and notice that $x^{2}+y^{2}+z^{2}+2(xy+yz+zx)=(x+y+z)^{2}=0$ .
If $x+y+z=0$ , show that (i) $2yz=x^{2}-y^{2}-z^{2}$ ; (ii) $(y^{2}+z^{2}-x^{2})(z^{2}+z^{2}-y^{2})(x^{2}+y^{2}-z^{2})+8x^{2}y^{2}z^{2}=0$ (iii) $ax^{2}+by^{2}+cz^{2}+2fyz+2gzx+2hxy$ can be expressed in the form $px^{2}+qy^{2}+rz^{2}$ ; and, find p, q, r in terms of a, b, c, f, g, h.

Cheers,

Nalin Pithwa.

Symmetric Functions. Alternating Functions. Algebra for RMO/IITJEE Math

Posted by Nalin Pithwa

Reference: Higher Algebra by Bernard and Child.

I. Symmetric Functions.

A function which is unaltered by the interchange of any two of the variables which it contains is said to be symmetric with respect to (wrt) these two variables.

Thus, $yz+zx+xy$ and $(x^{2}y+y^{2}z+z^{2}x)(x^{2}z+y^{2}z+z^{2}y)$ are symmetrical w.r.t. x, y, z.

The interchange of any two letters, x, y, z is called the transposition (xy).

Terms of an expression which are such that one can be changed into the other by one or more transpositions are said to be of the same type. Thus, all the terms of $x^{2}y+x^{2}z+y^{2}z+y^{2}x+z^{2}x+z^{2}y$ are of the same type, and the expression is symmetric with respect to x, y, z.

A symmetric function which is the sum of a number of terms of the same type is often written in an abbreviated form thus: Choose any one of the terms and place the letter $\Sigma$ (sigma) before it. For instance:

$x+y+z$ is represented by $\Sigma{x}$ and $xy+yz+zx$ by $\Sigma{xy}$ .

Again, $(x+y+z)^{2}=x^{2}+y^{2}+z^{2}+2xy+2yz+2zx=\Sigma{x^{2}}+2\Sigma{xy}$ .

It is obvious that

(i) if a term of some particular type occurs in a symmetric function, then all terms of the same type will also occur.

(ii) The sum, difference, product and quotient of two symmetric functions are also symmetric functions.

(PS: there is no need for a grand proof of the above; just apply the definitions of symmetric functions…check with some examples).

Considerations of symmetry greatly facilitate many algebraical processes as illustrated in the following examples:

Example 1: Expand $(y+z-x)(z+x-y)(x+y-z)$ .

Solution 1:

This expression is symmetric, homogeneous and of the third degree in x, y, z We may therefore assume that

$(y+z-x)(z+x-y)(x+y-z)= a.\Sigma{x^{3}}+b.\Sigma{x^{2}y}+cxyz$ , where a, b, c are independent of x, y, z. In this assumed identity:

(i) put $x=1, y=0, z=0$ , then $-1=a$

(ii) put $x=1, y=1, z=0$ , then $0=2a+2b$ , and so $b=1$ .

(iii) put $x=1, y=1, z=1$ , then $1=3a+6b+c$ and so $c=-2$ .

Hence, the required product is $-x^{2}-y^{2}-z^{2}+y^{2}z+yz^{2}+z^{2}x+zx^{2}+x^{2}y+xy^{2}-2xyz$ .

Example 2: Expand $(a+b+c+d)(ab+ac+ad+bc+bd+cd)$ . Test the result by putting $a=b=c=d=1$ .

Solution 2: the product is the sum of all terms of the product obtained by multiplying any one term of the first expression by any other term of the second expression. Hence, the result will have terms of the type : $a^{2}b, abc$ ,

The coefficient of $a^{2}b$ in the product is 1; because this term is obtained as product of a and ab and in no other way.

The coefficient of abc is 3; because this term is obtained in each of the three ways $a(bc), b(ca), c(ab)$ .

Hence, the required answer is $\Sigma{a^{2}b}+3\Sigma{abc}$

Test: The number of terms of the type $a^{2}b$ is 12 and the number of terms of the type abc is 4; hence, if $a=b=c=d=1$ , then $\Sigma{a}.\Sigma{ab}=4.6=24$ and $\Sigma{a^{2}b}+3.\Sigma{abc}=12+3.4=24$ so that the test is satisfied.

Example 3:

Factorize $(x+y+z)^{5}-x^{5}-y^{5}-z^{5}$ .

Solution 3:

Method I: Brute force is really difficult (I did give it a shot …:-))

Method II; Some of you might try the binomial theorem for positive integral index, but to extract the factors is still ..a little bit like brute force method only.

Method III:

Check whether the given expression is symmetric wrt any two variables (namely, x & y; y & z; z & x; ) and whether it is homogeneous and if so, what is the degree. Also from observations of past solved problems, we need to check how many terms of each type are there:

Observations are as follows: the degree of the expression is five only; and the expression is also homogeneous with each term being of degree five; to check for symmetry, let us proceed as follows:

$E_{1}=(x+y+z)^{5}-x^{5}-y^{5}-z^{5}$ and switching x and y gives us $E_{2}=(y+x+z)^{5}-y^{5}-x^{5}-z^{5}$ . Quite clearly, the expression is symmetric w.r.t. x and y; y and z; and, z and x.

To factorize it, we use fundamental theorem of algebra or factor or remainder theorem. Substitute $x=-y$ so that the expression is equal to $(z)^{5}-x^{5}-(-x)^{5}-z^{5}=z^{5}-x^{5}+x^{5}-z^{5}=0$ so that $(x+y)$ is a factor of the expression. Similarly, the other factors are $(y+z)$ and $(z+x)$ . By the fundamental theorem of algebra, we still need a quadratic factor of x, y and z. This factor should be homogeneous also. Hence, let

$E=(x+y+z)^{5}-x^{5}-y^{5}-z^{5}=(x+y)(y+z)(z+x){A(x^{2}+y^{2}+z^{2})+B(xy+yz+zx)}$ , where A and B are pure numeric coefficients independent of x, y and z.

So, put $x=1,y=1, z=0$ , then $2A+B=15$ and put $x=1, y=1, z=1$ , then $a+b=10$ so that $A=B=5$ .

So, $E=(x+y+z)^{5}-x^{5}-y^{5}-z^{5}=5(x+y)(y+z)(z+x)(x^{2}+y^{2}+z^{2}+xy+yz+zx)$ .

II Alternating Functions:

If a function E of x, y, z …is transformed into -E by the interchange of any two of the set x, y, z, …, then E is called an alternating function of x, y, z…(Note that just as in the case of symmetric functions, we talk of alternating functions w.r.t. a pair of variables at a time.)

((PS: At this juncture, it behooves you to recall the definitions of even and odd functions, and also to recall the fact that every function can be expressed as a sum of an even function and an odd function. Compare all three now: symmetric, alternating and even/odd functions. ))

Such an alternating function is $x^{n}(y-z)+y^{n}(z-x)+z^{n}(x-y)$ ; for, the interchange of any two letters, say x and y, transforms it into

$y^{n}(x--z)+x^{n}(x-y)+z^{n}(y-z)=-E$ .

Observe that the product and the quotient of two alternating functions are symmetric functions. (here, again, it does not require any grand proof…just pore over the definitions in your head…)

Thus, $\frac{x^{3}(y-z)+y^{3}(z-x)+z^{3}(x-y)}{(y-z)(z-x)(x-y)}$ is symmetric w.r.t. x, y, and z. (PS: please do some scribbling and verify this little observation/fact).

Example 1:

Factorize : $x^{3}(y-z)+y^{3}(z-x)+z^{3}(x-y)$ .

Solution 1:

Let $E=x^{3}(y-z)+y^{3}(z-x)+z^{3}(x-y)$

We know that $E=0$ when $x=y$ , $y=z$ and $z=y$ . Hence, the following is a factor of E: $(x-y)(y-z)(z-x)$ . As the given expression E is homogeneous of degree 4, it should have one more homogeneous linear factor. The only such factor possible is $K(x+y+z)$ . So, now,

$E=x^{3}(y-z)+y^{3}(z-x)+z^{3}(x-y)=K(x-y)(y-z)(z-x)(x+y+z)$ . To find K, the numerical coefficient independent of x, y, z, let us equate the coefficient of $x^{3}y$ on each side; then, $K=-1$ . (Alternatively, we could have substituted some numerical values for x, y, z and found K as it is an identity.)

Hence, $E=x^{3}(y-z)+y^{3}(z-x)+z^{3}(x-y)=-(x-y)(y-z)(z-x)(x+y+z)$ .

III. Cyclic Expressions:

An algebraic expression is said to be cyclic with respect to the letters a, b, c, d, …, h, k arranged in this order when it remains the same if we replace a by b, b by c, c by d, …., h by k, and k by a.

This “cycle of interchange of letters” is called the cyclic substitution denoted by $(abcd\ldots hk)$ .

(PS this reminds you of the the right hand unit vectors i, j, k and their cross products).

Thus, the expression $a^{2}b+b^{2}c+c^{2}d+d^{2}a$ is cyclic with respect to a, b, c, and d (in this order only) because the cyclic substitution $(abcd)$ changes the first term to the second term, the second term to the third term and the fourth term to the first term.

It is clear that:

(i) If a term of some particular type occurs in a cyclic expression, then the term which can be derived from this by the cyclic interchange, must also occur; and, the coefficients of these terms must be equal.

(ii) The sum, difference, product and quotient of two cyclic expressions is also cyclic.

In writing a cyclic expression, it is unnecessary to write the whole expression or all the terms explicitly. Thus, instead of writing the full $x^{2}(y-z)+y^{2}(z-x)+z^{2}(x-y)$ it suffices just to abbreviate it as $\Sigma{x^{2}(y-z)}$ . (Please note that the use of $\Sigma$ here has a different meaning than earlier.)

Sometimes, it is also written in short as $x^{2}(y-z)+\ldots+\ldots$ .

We need to be familiar with the following important basic cyclic identities:

$(b-c)+(c-a)+(a-b)=0$
$a(b-c)+b(c-a)+c(a-b)=0$
$a^{2}(b-c)+b^{2}(c-a)+c^{3}(a-b)=-(b-c)(c-a)(a-b)$ .
$bc(b-c)+ca(c-a)+ab(a-b)=-(b-c)(c-a)(a-b)$ .
$a(b^{2}-c^{2})+b(c^{2}-a^{2})+c(a^{2}-b^{2})=-(b-c)(c-a)(a-b)$ .
$a^{3}(b-c)+b^{3}(c-a)+c^{3}(a-b)=-(b-c)(c-a)(a-b)(a+b+c)$ .
$(a+b+c)(ab+bc+ca)=a(b^{2}+c^{2})+b(c^{2}+a^{2})+c(a^{2}+b^{2})+3abc$
$(b+c)(c+a)(a+b)=a(b^{2}+c^{2})+b(c^{2}+a^{2})+c(a^{2}+b^{2})+2abc$
$a^{3}+b^{3}+c^{3}-3abc=(a+b+c)(a^{2}+b^{2}+c^{2}-ab-bc-ca)$ .
$(b-c)^{2}+(c-a)^{2}+(a-b)^{2}=2(a^{2}+b^{2}+c^{2}-ab-bc-ca)$
$(a+b+c)(b+c-a)(c+a-b)(a+b-c)=-a^{4}-b^{4}-c^{4}+2b^{2}c^{2}+2c^{2}a^{2}+2a^{2}b^{2}$ .

Note that identity 9 can be proved by at least three non-trivial ways 🙂

PS again :-)) It helps to prove the above identities from LHS to RHS and also from RHS to LHS !!

it will be proved later that

i) Any symmetric function of $\alpha, \beta, \gamma$ can be expressed in terms of $\Sigma{\alpha}$ , $\Sigma{\alpha\beta}$ and $\alpha\beta\gamma$ .

ii) Any symmetric function of $\alpha, \beta, \gamma, \delta$ can be expressed in terms of $\Sigma{\alpha}$ , $\Sigma{\alpha\beta}$ , $\Sigma{\alpha\beta\gamma}$ , and $\alpha\beta\gamma\delta$ .

In the above two cases, the notation $\Sigma$ is used in the sense of a symmetric function.

This mode of expression is extremely useful in factorizing symmetric functions, and in proving identities:

Example 1:

Factorize $a(1-b^{2})(1-c^{2}) + b(1-c^{2})(1-a^{2}) + c(1-a^{2})(1-b^{2})-4abc$ .

Solution 1:

PS: Comment: this is not easy. But, go through it and there is ample scope to improve via exercises in the next blog 🙂

Denoting the given expression by E, we have

$E=a(1-(b^{2}+c^{2})+b^{2}c^{2})+\ldots+\ldots-4abc$

$E=\Sigma{a}-\Sigma{ab^{2}}+abc\Sigma{ab}-4abc$ , but from identity 7 above, we see that $\Sigma{ab^{2}}=\Sigma{a}.\Sigma{ab}-3abc$ ;

Hence, we get $E = \Sigma{a}-\Sigma{a}.\Sigma{ab}-abc+abc\Sigma{ab}$

So, $E=\Sigma{a}.(1-\Sigma{ab})-abc(1-\Sigma{ab})=(1-bc-ca-ab)(a+b+c-abc)$ .

IV. Substitutiions:

We consider processes by which one arrangement (permutation) of a set of elements may be transformed into another:

Taking the permutations $cdba, bdac$ of a, b, c, d, the first is changed into the second by replacing a by c, b by a, c by b and leaving a unaltered. This process is represented by the operator

$\left(\begin{array}{cccc}abcd\\cabd \end{array}\right)$ or $\left(\begin{array}{ccc}abc\\cab\end{array}\right)$

and, we write $\left(\begin{array}{ccc}abc\\cab\end{array}\right)cdba=bdac$ .

Such a process and also the operator which affects it is called a substitution.

As previously stated, the interchange of two elements a, b is called the transposition $(ab)$ .

Also, a substitution such as $\left(\begin{array}{cccc}abcd\\bcda\end{array}\right)$ in which each letter is replaced by the one immediately following it and the last by the first, is called a cyclic substitution or cycle, and is denoted by $(abcd)$ .

If two operators are connected by the sign =, the meaning is that one is equivalent to the other, thus $(abcd)=(bcda)$ .

Two or more substitutioins may be applied successively. This is indicated as follows, the order of operations being from right to left.

Let $S=(ab)$ , $T=(ba)$ , then $STabcd=Sacbd=bcad$ and $TSabcd=Tbacd=cabd$ . Thus, $ST=\left(\begin{array}{cccc}abcd\\bcad\end{array}\right)$ and $TS=\left(\begin{array}{cccc}abcd\\cabd\end{array}\right)$

This process is called multiplication of substitutions, and the resulting substitution is called the product.

Multiplication of this kind is not necessarily commutative, but if the substitutions have no common letter, it is commutative.

The operation indicated by $(ab)(ab)$ , in which $(ab)$ is performed twice, produces no change in the order of the letters, and is called an identical substitution.

Any substituion is cyclic or is the product of two or more cyclic substitutions which have no common element. As an instance, consider the substitution $S = \left(\begin{array}{ccccccccc}abcdefghk\\chfbgaedk\end{array}\right)$

Here, a is changed to c, c to f, f to a, thus completing the cycle $(acf)$ . Also, b is changed to h, h to d, d to b, making the cycle $(bhd)$ . Next, c is changed to g, and g to e, giving the cycle $(eg)$ . The element k is unchanged, and we write

$S=(acf)(bhd)(eg)(k)$ or $S=(acf)(bhd)(eg)$ .

This expression for S in unique, and the order of the factors is indifferent. Moreover, the method applies universally, for in effecting any substitution, we must arrive at a stage when some letter is replaced by the first, thus completing a cycle. The same argument applies to the set of letters not contained in the cycle.

A cyclic substitution of n elements is the product of $(n-1)$ transpositions:

Consider

$(abc)=(ab)(bc)$ , $(abcd)=(abc)(cd)=(ab)(bc)(cd)$ , $(abcde)=(abcd)(de)=(ab)(bc)(cd)(de)$ , and so on.

We also have equalities such as : $(ae)(ad)(ac)(ab)=(abcde)$ and $(ab)(ac)(ad)(ae)=(edcba)$ .

A substitution which deranges n letters and which is the product of r cycles is equivalent to $(n-r)$ transpositions.

This follows at once from our previous work. Thus, if $S = \left(\begin{array}{cccccccc}abcdefgh\\chfbgaed\end{array}\right)$ , then

$S=(acf)(bhd)(eg)=(ac)(cf)(bh)(hd)(eg)$ .

If we introduce the product $(ab)(ab)$ , S is unaltered and the number of transpositions is increased by 2.

Thus, if a given substitutition is equivalent to j transpositions, the number j is not unique. We shall prove that : $j=n-r+2s$ where r is a positive integer or zero.

This is a very important theorem, and to prove it we introduce the notion of “inversions.”

*** Taking the elements a, b, c, d, e choose some arrangement, as $abcde$ , and call it a normal arrangement.

Consider the arrangement $bdeac$ . Here b precedes a, but follows it in the normal arrangement. On this account, we say that the pair ba constitutes an inversion.

Thus, $bdeac$ contains five inversions, namely, $ba, da, dc, ea, ec$ .

Theorem 1:

If i is the number of inversions which are introduced or removed by a substitution which is equivalent to j transpositions, then i and j are both even or both odd.

Proof of theorem 1:

Consider the effect of a single transposition $(fg)$ .

If f, g are consecutive elements, the transposition $(fg)$ does not alter the position of f or g relative to the other elements. It therefore introduces or removes a single inversion due to the interchange of f, g.

If f, g are separated by n elements p, q, r, …, x, then f can be moved to the place occupied by g by $n+1$ interchanges of consecutive elements, and then g can be moved to the place originally occupied by f by n such interchanges.

Thus, the transposition $(fg)$ can be effected by $2n+1$ interchanges of consecutive elements. Therefore, any transposition introduces or removes an odd number of inversions, and the theorem follows. QED.

Again, for a given substitution, i is a fixed number, and therefore whatever value j may have, it must be even or odd, according as i is even or odd. Hence, we get the following:

Theorem 2:

If one arrangement A of a given set of elements is changed into another B by j transpositions, then j is always even or always odd. In other words: the number of transpositions which are equivalent to a given substitution is not unique, but is always even or always odd.

The minimum value of j is $n-r$ .

Thus, substitutions may be divided into two distinct classes. We say that a substitution is even or odd according as it is equivalent to an even or an odd number of transpositions.

Rule:

To determine the class of a substitution S we may express it as the product of cycles, and count the number of cycles with an even number of elements: then S is even or odd according as this number is even or odd.

Or, we can settle the question by counting the number of inversions, but this generally takes longer.

The tutorial exercises follow this blog.

Cheers,

Nalin Pithwa

A fifth degree equation in two variables: a clever solution

Posted by Nalin Pithwa

Question:

Verify the identity: $(2xy+(x^{2}-2y^{2}))^{5}+(2xy-(x^{2}-2y^{2}))^{5}=(2xy+(x^{2}+2y^{2})i)^{5}+(2xy-(x^{2}+2y^{2})i)^{5}$

let us observe first that each of the fifth degree expression is just a quadratic in two variables x and y. Let us say the above identity to be verified is:

$P_{1}+P_{2}=P_{3}+P_{4}$

Method I:

Use binomial expansion. It is a very longish tedious method.

Method II:

Factorize each of the quadratic expressions $P_{1}, P_{2}, P_{3}, P_{4}$ using quadratic formula method (what is known in India as Sridhar Acharya’s method):

Now fill in the above details.

You will conclude very happily that :

The above identity is transformed to :

$P_{1}=(x+y+\sqrt{3}y)^{5}(x+y-\sqrt{3}y)^{5}$

$P_{2}=(-1)^{5}(x-y-\sqrt{3}y)^{5}(x-y+\sqrt{3}y)^{5}$

$P_{3}=(i^{2}(x-y-\sqrt{3}y)(x-y+\sqrt{3}y))^{5}$

$P_{4}=((-i^{2})(x+y+\sqrt{3}y)(x-y-\sqrt{3}y))^{5}$

You will find that $P_{1}=P_{4}$ and $P_{2}=P_{4}$

Hence, it is verified that the given identity $P_{1}+P_{2}=P_{3}+P_{4}$ . QED.

Regards,
Nalin Pithwa.

Set Theory, Relations, Functions: preliminaries: part 10: more tutorial problems for practice

Posted by Nalin Pithwa

Problem 1:

Prove that a function f is 1-1 iff $f^{-1}(f(A))=A$ for all $A \subset X$ . Given that $f: X \longrightarrow Y$ .

Problem 2:

Prove that a function if is onto iff $f(f^{-1}(C))=C$ for all $C \subset Y$ . Given that $f: X \longrightarrow Y$ .

Problem 3:

(a) How many functions are there from a non-empty set S into $\phi$ \?

(b) How many functions are there from $\phi$ into an arbitrary set $S$ ?

Problem 4:

Let $f: X \longrightarrow Y$ be a function, let $A \subset X$ , $B \subset X$ , $C \subset Y$ and $D \subset Y$ . Prove that

i) $f(A \bigcap B) \subset f(A) \bigcap f(B)$

ii) $f^{-1}(f(A)) \supset A$

iii) $f(f^{-1}(C)) \subset C$

Problem 5:

Let I be a non-empty set and for each $i \in I$ , let $X_{i}$ be a set. Prove that

(a) for any set B, we have $B \bigcap \bigcup_{i \in I}X_{i}=\bigcup_{i \in I}(B \bigcap X_{i})$

(b) if each $X_{i}$ is a subset of a given set S, then $(\bigcup_{i \in I}X_{i})^{'}=\bigcap_{i \in I}(X_{i})^{'}$ where the prime indicates complement.

Problem 6:

Let A, B, C be subsets of a set S. Prove the following statements:

(i) $A- (B-C)=(A-B)\bigcup(A \bigcap B \bigcap C)$

(ii) $(A-B) \times C=(A \times C)-(B \times C)$

🙂 🙂 🙂

Nalin Pithwa

Set Theory, Relations, Functions: Preliminaries: Part IX: (tutorial problems)

Posted by Nalin Pithwa

Reference: Introductory Real Analysis, Kolmogorov and Fomin, Dover Publications.

Problem 1:

Prove that if $A \bigcup B=A$ and $A \bigcap B=A$ , then $A=B$ .

Problem 2:

Show that in general $(A-B)\bigcup B \neq A$ .

Problem 3:

Let $A = \{ 2,4, \ldots, 2n, \ldots\}$ and $B= \{ 3,6,\ldots, 3n, \ldots\}$ . Find $A \bigcap B$ and $A - B$ .

Problem 4:

Prove that (a) $(A-B)\bigcap (C)=(A \bigcap C)-(B \bigcap C)$

Prove that (b) $A \Delta B = (A \bigcup B)-(A \bigcap B)$

Problem 5:

Prove that $\bigcup_{a}A_{\alpha}-\bigcup_{a}B_{\alpha}=\bigcup_{\alpha}(A_{\alpha}-B_{\alpha})$

Problem 6:

Let $A_{n}$ be the set of all positive integers divisible by $n$ . Find the sets (i) $\bigcup_{n=2}^{\infty}A_{n}$ (ii) $\bigcap_{n=2}^{\infty}A_{n}$ .

Problem 7:

Find (i) $\bigcup_{n=1}^{\infty}[n+\frac{1}{n}, n - \frac{1}{n}]$ (ii) $\bigcap_{n=1}^{\infty}(a-\frac{1}{n},b+\frac{1}{n})$

Problem 8:

Let $A_{\alpha}$ be the set of points lying on the curve $y=\frac{1}{x^{\alpha}}$ where $(0<x<\infty)$ . What is $\bigcap_{\alpha \geq 1}A_{\alpha}$ ?

Problem 9:

Let $y=f(x) = <x>$ for all real x, where $<x>$ is the fractional part of x. Prove that every closed interval of length 1 has the same image under f. What is the image? Is f one-to-one? What is the pre-image of the interval $\frac{1}{4} \leq y \leq \frac{3}{4}$ ? Partition the real line into classes of points with the same image.

Problem 10:

Given a set M, let $\mathscr{R}$ be the set of all ordered pairs on the form $(a,a)$ with $a \in M$ , and let $aRb$ if and only if $(a,b) \in \mathscr{R}$ . Interpret the relation R.

Problem 11:

Give an example of a binary relation which is:

Reflexive and symmetric, but not transitive.
Reflexive, but neither symmetric nor transitive.
Symmetric, but neither reflexive nor transitive.
Transitive, but neither reflexive nor symmetric.

We will continue later, 🙂 🙂 🙂

PS: The above problem set, in my opinion, will be very useful to candidates appearing for the Chennai Mathematical Institute Entrance Exam also.

Nalin Pithwa

A quadratic and trigonometry combo question: RMO and IITJEE maths coaching

Posted by Nalin Pithwa

Question:

Given that $\tan {A}$ and $\tan {B}$ are the roots of the quadratic equation $x^{2}+px+q=0$ , find the value of

$\sin^{2}{(A+B)}+ p \sin{(A+B)}\cos{(A+B)} + q\cos^{2}{(A+B)}$

Solution:

Let $\alpha=\tan{A}$ and $\beta=\tan{B}$ be the two roots of the given quadratic equation: $x^{2}+px+q=0$

By Viete’s relations between roots and coefficients:

$\alpha+\beta=\tan{A}+\tan{B}=-p$ and $\alpha \beta = \tan{A}\tan{B}=q$ but we also know that $\tan{(A+B)}=\frac{\tan{A}+\tan{B}}{1-\tan{A}\tan{B}}=\frac{-p}{1-q}=\frac{p}{q-1}$

Now, let us call $E=\sin^{2}{(A+B)}+p\sin{(A+B)\cos{(A+B)}}+\cos^{2}{(A+B)}$ which in turn is same as

$\cos^{2}{(A+B)}(\tan^{2}{(A+B)}+p\tan{(A+B)}+q)$

We have already determined $\tan{(A+B)}$ in terms of p and q above.

Now, again note that $\sin^{2}{\theta}+\cos^{2}{\theta}=1$ which in turn gives us that $\tan^{2}{\theta}+1=\sec^{2}{\theta}$ so we get:

$\sec^{2}{(A+B)}=1+\tan^{2}{(A+B)}=1+\frac{p^{2}}{(q-1)^{2}}=\frac{p^{2}+(q-1)^{2}}{(q-1)^{2}}$ so that

$\cos^{2}{(A+B)}=\frac{1}{\sec^{2}{(A+B)}}=\frac{(q-1)^{2}}{p^{2}+(q-1)^{2}}$

Hence, the given expression E becomes:

$(\frac{(q-1)^{2}}{p^{2}+(q-1)^{2}})(\frac{p^{2}}{(q-1)^{2}}+\frac{p^{2}}{q-1}+q)$ , which is the desired solution.

🙂 🙂 🙂

Nalin Pithwa.

Set theory, relations, functions: preliminaries: part VI

Posted by Nalin Pithwa

Set theory, functions, relations: part VI

Set Theory, Relations, Functions: preliminaries part VI

Posted by Nalin Pithwa

Set theory, functions, relations: part VI

For the love of Maths: the Queen of all Sciences

Indian Statistical Institute Entrance Exam

Meaning of function or mapping or transformation in brief words

III. Tutorial problems. Symmetric and alternating functions. RMO and IITJEE math

Tutorial problems. I. Symmetric and Alternating functions. RMO/IITJEE Math

Symmetric Functions. Alternating Functions. Algebra for RMO/IITJEE Math

A fifth degree equation in two variables: a clever solution

Set Theory, Relations, Functions: preliminaries: part 10: more tutorial problems for practice

Set Theory, Relations, Functions: Preliminaries: Part IX: (tutorial problems)

A quadratic and trigonometry combo question: RMO and IITJEE maths coaching

Set theory, relations, functions: preliminaries: part VI

Set Theory, Relations, Functions: preliminaries part VI