Results 1 to 5 of 5

Math Help - Solving linear system under Z_p

  1. #1
    Newbie
    Joined
    Mar 2006
    Posts
    7

    Solving linear system under Z_p

    Hi all, I need help with solving a linear system in a finite field, Z_7 and Z_11.

    The original given linear system is

    2x + 4y - 2z = 1
    2x + y + z = 3
    5x - 3y + 7z = 0

    Under positive representation for Z_7 and Z_11, I get the following linear systems respectively

    2x + 4y + 5z = 1
    2x + y + z = 3
    5x + 4y = 0

    and

    2x + 4y + 9z = 1
    2x + y + z = 3
    5x + 8y +7z = 0

    I did the usual gaussian elimination, keeping all the coefficients in Z_7 and Z_11 respectively, and I got
    Z_7: x = 0, y = 0, z = 3, determinant = 6
    Z_11: x = 9, y = 5, z = 2, determinant = 6

    The solutions my teacher gave were
    Z_7: x = 0, y = 0, z = 4, determinant = 6
    Z_11: x = 10, y = 8, z = 1, determinant = 6

    However, I substituted his solutions into the respective linear systems, and they don't seem to be correct.

    For example, for Z_7, for the equation
    2x+y+z = 3, I get 2(0) + (0) + (4) = 4 != 3

    For Z_11, for the equation
    2x+y+z = 3, I get 2(10) + (8) + (1) = 7 != 3

    Where did I go wrong?

    Thank you.

    Regards,
    Rayne
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by wu_weidong View Post
    2x + 4y - 2z = 1
    2x + y + z = 3
    5x - 3y + 7z = 0
    Well, let's see what happens if you don't do anything fancy and solve this by substitution. I'm going to do this little step by little step as I get screwed up when I skip steps. I'll do this for Z_7.

    2x + 4y + 5z = 1
    2x + y + z = 3
    5x + 4y = 0

    Solving the bottom equation we get:
    5x + 4y = 0

    5x + 4y + 3y = 0 + 3y

    5x = 3y

    In Z_7 the multiplicative inverse of 5 is 3, so:
    3(5x) = 3(3y)

    x = 2y

    Put x = 2y into the remaining equations:
    2(2y) + 4y + 5z = 1 ==> 4y + 4y + 5z = 1
    2(2y) + y + z = 3 ==> 4y + y + z = 3

    Which leads to
    y + 5z = 1
    5y + z = 3

    I'm going to solve the bottom equation for z.
    5y + z = 3

    2y + 5y + z = 2y + 3

    z = 2y + 3

    Put this into the top equation:
    y + 5(2y + 3) = 1

    y + 3y + 1 = 1

    4y + 1 = 1

    4y + 1 + 6 = 1 + 6

    4y = 0

    Since Z_7 has no zero divisors, I get that y = 0.

    z = 2(0) + 3 = 3

    x = 2(0) = 0

    So x = 0, y = 0, z = 3.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by wu_weidong View Post
    2x + 4y - 2z = 1
    2x + y + z = 3
    5x - 3y + 7z = 0
    I'll do it this time for Z_11 and by the method of adding and subtracting equations.
    2x + 4y + 9z = 1
    2x + y + z = 3
    5x +8y + 7z = 0

    I'll start by considering the top and middle equations:
    2x + 4y + 9z = 1
    2x + y + z = 3

    We can subtract these to eliminate x. So:
    3y + 8z = 9

    Thus our system is:
    2x + 4y + 9z = 1
    (0)x + 3y + 8z = 9
    5x +8y + 7z = 0

    Now for the top and bottom equations:
    2x + 4y + 9z = 1
    5x +8y + 7z = 0 ==> 7(5x + 8y + 7z) = 7(0)

    2x + 4y + 9z = 1
    2x + y + 5z = 0

    Now subtract:
    3y + 4z = 1

    Now our system is:
    2x + 4y + 9z = 1
    (0)x + 3y + 8z = 9
    (0)x + 3y + 4z = 1

    Now subtract the middle and bottom equations to eliminate y:
    4z = 8

    z = 2.

    Our system is
    2x + 4y + 9z = 1
    (0)x + 3y + 8z = 9
    (0)x + (0)y + z = 2

    Now for back substitution:
    z = 2

    3y + 8(2) = 9

    So
    3y + 5 = 9

    3y + 5 + 6 = 9 + 6

    3y = 4

    4(3y) = 4(4)

    y = 5

    So
    2x + 4y + 9z = 1

    2x + 4(5) + 9(2) = 1

    2x + 9 + 7 = 1

    2x + 5 = 1

    2x + 5 + 6 = 1 + 6

    2x = 7

    6(2x) = 6(7)

    x = 9

    Thus
    x = 9, y = 5, z = 2

    (So I agree with both of your solutions.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2006
    Posts
    7
    Quote Originally Posted by topsquark View Post

    (So I agree with both of your solutions.)

    -Dan
    Thank you. That's why I didn't understand my teacher's answers, and he insisted they were correct.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    I think you can also use Cramer's rule here.

    Because since Z_7 and Z_11 are finite fields the set of all solutions forms a proper vector space and hence the theorems from linear algebra will apply.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving system of linear equations
    Posted in the Algebra Forum
    Replies: 4
    Last Post: April 5th 2011, 08:12 AM
  2. Solving a system of linear equations.
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: September 21st 2010, 05:17 PM
  3. solving a system of linear equations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 18th 2010, 08:56 AM
  4. solving a linear system by graphing
    Posted in the Math Topics Forum
    Replies: 13
    Last Post: January 25th 2006, 01:26 PM
  5. Solving a linear system by substitution
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 25th 2006, 10:21 AM

Search Tags


/mathhelpforum @mathhelpforum