O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

3.9 GAUSSIAN ELIMINATION

Let A = (ai,j be an n × n matrix and x = (x1, x2,…, xn), y = (y1, y2,…, yn) be n-vectors, all with real number entries satisfying

image

If det(A) ≠ 0, then for every y, the linear system of Equations (3.20) has a unique solution x,

image

Gaussian elimination is a process in which transformations are applied to an invertible matrix A to produce the identity matrix I and thereby obtain the solution for x in Equation (3.20).

3.9.1 Elementary Row and Column Matrix Transformations

  1. Rr,s(v) (r ≠ s) is the n × n matrix equal to the identity matrix, except that the element in position (r, s) of Rr,s(v) is v. For example when n = 4

    image

    If

    image

    then

    image

    Premultiplication of A by Rr, s(v) replaces the rth row of A by the sum of

    • v times the sth row of A and
    • The rth row of A.

      The inverse of Rr, s(v) is Rr, s(− v).

  2. Cr, s(v) (r ≠ s) is the n × n matrix, which is equal to the identity matrix except that the element in position (r, s) of Cr,s(v) is v. For example, when n = 4

    If

    then

    Postmultiplication ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required