ALGEBRA

74 flashcards · Other · by Minh Đức

1. dot product of vector A(a1,a2) and vector B (b1,b2) is a1.b1 + a2.b2

2. norm of vector A(n1,n2,n3,....n) is what ?

   sqrt(n1^2 + n2^2 + ..... n^2)

3. if vector u and v are orthorogal, so u.v = 0 and the angle between them is 90

4. let Phi is the angle between 2 vector u and v. cos(Phi) = ?

   (u- . v-) / ([u].[v])

5. when will a les has no solution

   when the last row is 0, but the value of that row is != 0

6. when will a les has 1 solution

   rank = numbers of variables

7. when will a les has infinite solutions

   rank < numbers of variables

8. how to A-1 of A

   convert (A|I) to (I| A-1)

9. when a matrix is not invertible

   equal row equal column zero row

10. how to find the determinant of m*n matrix

    pick a row or column that contains the most 0s take the sum of all the element with their cofactors

11. If a multiple of one row (column) of A is added to another row (column) to produce a matrix B, then det (B) = det(A) If two rows of A are interchanged to produce B, then det(B) = -det(A) If one row of A is multiplied by k to produce B, then det(B) = k.det(A)

12. if A is a diagonal matrix, upper triangular or lower triangular ,det(A) = product of the main diagonal

13. det(I) = 1

14. det(A.B) = det(A).det(B)

15. det(A-1) = 1/det(A)

16. A n*n, det(k .A) = k^n.det(A)

17. det(A + B) != det(A) + det(B)

18. when a A is invertible/regular => det(A) != 0, Ax =b has unique solution

19. when will the determinant of a matrix is equal to 0

    consist of 0 row(column) equal row or equal column one row is a multiple of another row one row is linear combination of other rows

20. how to find solution for les by using determinant

    x = |d1| / |A|, y = |d2| / |A|, ..... n = |dn| / |A|. d1,d2,dn is the matrix that we obtain when replace the b column to the ith column of A

21. how to find inverse of a matrix by using determinant

    adj(A) / det(A)

22. how to find adjoint of a matrix

    transpose of the cofactor of matrix A

23. how to find the area of parallelogram by using determinant for vector a(1,2) and b(3,4)

    abs(det({1,3}, {2,4})

24. how to find volumn of parrallelogram spanded by vectors: v1,v2,v3,...,vn

    det(v1,v2,...,vn)

25. check for linearly dependent or not? det = 0 -> dependent, det != 0 -> independent

26. how to prove subspace

    check does it contain zero check does it close under addition check does it close under multiplication

27. a few properties of linenearly dependence: null is linearly independent {0} is linearly dependent

28. let S be a spanning set of a vector space V with K elements. Any set of K' > K elements is linearly dependent.

29. any basis of 1 vector space have the same number of elements

30. number of elements in a basis of V is called what ?

    the dimension of V

31. when S will be basis of V

    span(S) = V S is linearly independent

32. S is a basis of V, u belongs to V, so u is linear combination of elements of S

33. let S = {v1,v2,...,vk} be a basis for V. u = a1.v1 + a2.v2 + a3.v3 + ....... so what (a1,a2,a3,....,ak) is called ?

    coordinates of u corresponding to the basis

34. If S = {v1,v2,...,vk} is a spanning set of V and if S is a maximal subset of linearly independent elements, then S is a basis of V

35. given matrix A, what is null space of A ?

    set of all solution in Ax = 0

36. given matrix A, what is column(row) space of A ?

    all linear combinations of the column(row) of A

37. if xp is solution to Ax = b. So every soltution of Ax = b can be written as x=xp+xh where Xh is solution of homonogenous equation.

38. for finding basis for Null(A)

    1. Find the reduced echelon-form 2. Write dependent variables in terms of free variables 3. Find general solution to Ax = 0 in term of free variables. 4. Decompose the general solution vector into a linear combination of vectors where the coefficients are the free variables. 5. Vectors in the above step form a basis for Null(A)

39. for finding basis for column(row) of A

    transform A into row echolon form basis of column(row) is spanning set of pivot - row(column) of (A)

40. how to find null space of A

    N(A) = N(rref(A)) write free variables in terms of dependent variables write solution set in terms of linear combination of free variables N(A) = span({vectors of free variables in step 3})

41. when will it be linearly independent

    Ax = 0 has one unique solution 0 N(A) contains only 0 det(A) != 0

42. what is dim(N(A))

    number of non pivot columns

43. what is dim(C(A))

    = dim(row(A)) = rank = numbers of pivots

44. what to check to prove linear mapping

    f(a+b) = f(a) + f(b) f(c.a) = c.f(a)

45. matrix form for rotation counter clockwise. A =

    cos -sin sin cos

46. matrix form for rotation clockwise A =

    cos sin -sin cos

47. ways to check properties of relation on a matrix reflexive symmetric antisymmetric transitive

    diagonal must be 1 it is symmetric through the diagonal the elements that reflect through diagonal must be either 0 or both 0, cannot be both 1 the product of the square matrix must be a subset of the initial matrix

48. how to find transitive closure by using matrix representation ( naive algortihm) , with |A| = n

    M1 or M2 ..... Mn ( boolean disjunction) if Mi+1 = Mi then stop and just take into account from M1 to Mi

49. how to find transitive closure by using Warshall algorithm

    find Mn recursively Mn = Mn-1 + các pair có elementh thứ n làm trung gian

50. what is partial ordering relation

    relation that is reflexive antisymmetric transitive

51. given a set A and a partial order relation R, a,b belongs to A a,b are comparable when ............ otherwise they are ............

    aRb or bRa (linearly ordered) incomparable

52. if p is a prime number and p | a.b => ?

    p | a and p | b

53. if p is a prime number and p | a^r => ?

    p | a

54. how to find gcd(a,b) and lcm(a,b)

    factorise a and b into product of prime number gcd = product of the primes with min power lcm = product of the primes with max power

55. euler toition function , if p,q is a prime number phi ( p ) = phi ( pk ) = phi (p.q) =

    p - 1 pk - pk-1 (p-1) (q-1)

56. (a+b) mod n =

    (a mod n + b mod n ) mod n

57. (a.b) mod n =

    (a mod n . b mod n ) mod n

58. ar mod n =

    (a mod n)r mod n

59. Fermat little theorem:

    ap-1 == 1 mod p if p is prime and a is not divisible by p describe the initial power to the p-1

60. a^n mod b, there are 2 ways to calculate, ferma little and human method, when to use each one ferma little: .......... human method:.......

    if b is prime if b is not prime

61. for calculating exponential modular, when using human method, how to do it ?

    tìm a1,2,3,4 sao cho an mod n = 1(best), -1(quite good), -2 ,2 biễu diễn số mũ ban đầu theo n

62. quick way to check relative prime

    use euclid method , gcd(a,b) = 1 then a and b are relative prime

63. according to euclid algo: gcd(a,b) =

    gcd(b, a mod b)

64. euler theorem:

    aphi(n) mod n = 1

65. properties of a group (G,*)

    closed under * associative has the identity element such that a* I = a

66. what is order of a group

    the number of elements in that group

67. the order of the group (Zn*, *) is

    phi(n)

68. if p is a prime then ap congruent a mod p

69. an element a of group Zn is multiplicative inverse iff

    gcd(n,a) = 1

70. for ceasar cipher: k is private key, using modulo n encryption: decryption:

    y = (x+k) mod n x = (y-k) mod n

71. for turing cipher version 2: k is private key, using modulo n encryption: decryption: conditon for k:

    y = (x.k) mod n x = (k-1 * y) mod n gcd(k,n) = 1

72. for the affine cipher: k = (a,b) is private key, using modulo n: encryption: decryption: condition:

    y = (ax+b) mod n x =a-1(x-b) mod n gcd(a,n) = 1

73. Steps of choosing keys for RSA cryptosystem:

    step 1: choose p and q are large co-prime step 2: n = p.q step 3: choose public key e such that gcd(e, phi(n)) = 1 step 4: choose private key d such that e.d = 1 mod(phi(n))

74. RSA cryptography with x is the plain text, e is public key, d is private key, modulo n ecryption: decryption:

    ecryption: y = xe mod n decryption: x = yd mod n