Cryptography

Transposition A transposition is an exchange of two objectsin a list of objects.Examples:ABCD21453ACBD12453“Transposition"isanothermathematicalterm,andisnot the same as matrix tranpose.kshumENGG2013

Transposition • A transposition is an exchange of two objects in a list of objects. kshum ENGG2013 A B C D A C B D Examples: 2 1 4 5 3 1 2 4 5 3 “Transposition” is another mathematical term, and is not the same as matrix tranpose

Anotherpatterna11a12=a11a22—a12a21a21a22a11a12a13a21a22a23a31a32a33=a11a22a33—a11a23a32—a12a21a33+a12a23a31+a13a21a32—a13a22a31 The sign of each term is closely related to thenumber of transpositions required to obtainthe second subscripts, starting from (1,2) forthe 2x2 case or (1,2,3) for the 3x3 case.kshumENGG2013

Another pattern • The sign of each term is closely related to the number of transpositions required to obtain the second subscripts, starting from (1,2) for the 2x2 case or (1,2,3) for the 3x3 case. kshum ENGG2013

The sign Let p(1), p(2), .., p(n) be an order of 1,2,..,n.- For example p(1)=3, p(2) = 2, p(3)=1 is an orderingof 1, 2, 3. Starting from (1,2,...,n),if we need an odd no.of transpositions to get ( p(1), p(2), ..., p(n) ),we define the sign of (p(1), p(2),..,p(n) be -1. Otherwise, if we need an even no. oftranspositionsto get ( p(1), p(2), ..., p(n) ), wedefine the sign of (p(1), p(2),..,p(n)) be +1.kshumENGG2013

The sign • Let p(1), p(2), ., p(n) be an order of 1,2,.,n. – For example p(1)=3, p(2) = 2, p(3)=1 is an ordering of 1, 2, 3. • Starting from (1,2,.,n), if we need an odd no. of transpositions to get ( p(1), p(2), ., p(n) ), we define the sign of (p(1), p(2),.,p(n)) be –1. • Otherwise, if we need an even no. of transpositions to get ( p(1), p(2), ., p(n) ), we define the sign of (p(1), p(2),.,p(n)) be +1. kshum ENGG2013

Definition of nxn determinant±1a11a12aina21a2na22sgn(p)a1p(1)a2p(2)a3p(3) : : · anp(n):pan1annan2The summation is over all n! possibleorderings p = (p(1), p(2), ..., p(n) ) of 1,2,...,n.-There are n!terms. sgn(p) is either +1 or -1, usually called thesignature or signum of p.kshumENGG2013

Definition of nn determinant • The summation is over all n! possible orderings p = ( p(1), p(2), ., p(n) ) of 1,2,.,n. – There are n! terms. • sgn(p) is either +1 or –1, usually called the signature or signum of p. kshum ENGG2013 1

Properties of determinantDeterminant of nxn identity matrix equals 1 Exchange two rows (or columns) → multiplydeterminant by -1.Multiply a row (or a column) by a constant k→ multiply the determinant by k. Add a constant multiple of a row (column)toanother row (column) no change Additive property as in the 3x3 and 2x2 case.kshumENGG2013

Properties of determinant • Determinant of nn identity matrix equals 1. • Exchange two rows (or columns) → multiply determinant by –1. • Multiply a row (or a column) by a constant k → multiply the determinant by k. • Add a constant multiple of a row (column) to another row (column) → no change • Additive property as in the 33 and 22 case. kshum ENGG2013