Loading [MathJax]/jax/output/HTML-CSS/jax.js
Ask Your Question
0

Solving multiple linear equation in Sagemath

asked 0 years ago

anonymous user

Anonymous

updated 0 years ago

dan_fulea gravatar image

.

var('a b c d p q r s')

f1 = 14*a - 102*b + 104*c + 24*d

f2 =   -7*a + 51*b - 52*c - 12*d

f3 = -52*a - 12*b - 142*c - 138*d

f4 = 26*a + 6*b + 71*c + 69*d

f5 = 28*a - 204*b + 208*c + 48*d 

f6 = -14*a + 102*b - 104*c - 24*d 

f7 = -104*a - 24*b - 284*c - 276*d

f8 = 52*a + 12*b + 142*c + 138*d

f9 =  204*a - 292*b - 48*c + 176*d

f10 = -102*a + 146*b + 24*c - 88*d

f11 = 24*a - 88*b + 276*c - 556*d

f12 = -12*a + 44*b - 138*c + 278*d 

f13 = 408*a - 584*b - 96*c + 352*d

f14 = -204*a + 292*b + 48*c - 176*d

f15 = 48*a - 176*b + 552*c - 1112*d

f16 = -24*a + 88*b - 276*c + 556*d

solve([f1==0, f2==0, f3==0, f4==0, f5==0, f6==0, f7==0, f8==0, 
       f9==0, f10==0, f11==0, f12==0, f13==0, f14==0, f15==0, f16==0], a, b ,c, d)

I am trying to solve these 16 system of equations but not getting any result. Please help regarding this

Preview: (hide)

Comments

Why should there be any solution of the many equations in only four variables, a,b,c,d?

dan_fulea gravatar imagedan_fulea ( 0 years ago )

2 Answers

Sort by » oldest newest most voted
2

answered 0 years ago

dan_fulea gravatar image

Let us see what happens, and which equations can be eliminated with bare hands.

First of all, there are some simple dependencies. I have copy+pasted the variable declaration (and we need only a b c d and not also the other variables) and the man linear expressions in them, that are finally made equations.

sage: bool(f1 == -2*f2)
True

So we only keep the simpler f2 and forget about f1.

sage: bool(f3 == -2*f4)
True

So we only keep the simpler f4 and forget about f3.

sage: bool(f5 == -2*f6)
True

So we only keep the simpler f6 and forget about f5.

sage: bool(f7 == -2*f8)
True

So we only keep the simpler f8 and forget about f7.

sage: bool(f9 == -2*f10)
True

So we only keep the simpler f12 and forget about f11.

sage: bool(f11 == -2*f12)
True

So we only keep the simpler f10 and forget about f9.

sage: bool(f13 == -2*f14)
True

So we only keep the simpler f14 and forget about f13.

sage: bool(f15 == -2*f16)
True

So we only keep the simpler f16 and forget about f15.


We test that the remained homogeneous system still has only the trivial solution:

equations = [f == 0 for f in [f2, f4, f6, f8, f10, f12, f14, f16]]
solve(equations, [a, b, c, d])

This delivers:

[[a == 0, b == 0, c == 0, d == 0]]

sage: equations
[-7*a + 51*b - 52*c - 12*d == 0,
 26*a + 6*b + 71*c + 69*d == 0,
 -14*a + 102*b - 104*c - 24*d == 0,
 52*a + 12*b + 142*c + 138*d == 0,
 -102*a + 146*b + 24*c - 88*d == 0,
 -12*a + 44*b - 138*c + 278*d == 0,
 -204*a + 292*b + 48*c - 176*d == 0,
 -24*a + 88*b - 276*c + 556*d == 0]

So above i printed again the remained equations. We observe that there are further easy dependencies:

sage: bool(2*f2 == f6)
True
sage: bool(2*f4 == f8)
True
sage: bool(2*f10 == f14)
True
sage: bool(2*f12 == f16)
True

So we keep only the easier equations, and ask again about solutions of the simplified system...


equations = [f == 0 for f in [f2, f4, f10, f12]]
solve(equations, [a, b, c, d])

And indeed:

sage: equations = [f == 0 for f in [f2, f4, f10, f12]]
sage: solve(equations, [a, b, c, d])
[[a == 0, b == 0, c == 0, d == 0]]

So the given system is equivalent to the system of the isolated four equations:

sage: equations
[-7*a + 51*b - 52*c - 12*d == 0,
 26*a + 6*b + 71*c + 69*d == 0,
 -102*a + 146*b + 24*c - 88*d == 0,
 -12*a + 44*b - 138*c + 278*d == 0]

The matrix of the system is:

A = matrix(QQ, 4, 4, [
    [-7, 51, -52, -12],
    [26, 6, 71, 69],
    [-102, 146, 24, -88],
    [-12, 44, -138, 278], ])
A.det()

And we obtain a non-zero determinant:

-186674544
sage: A.det().factor()
-1 * 2^4 * 3^5 * 7 * 19^3

So the homogeneous system has only the trivial solution.


An other approach would be to isolate the coefficients of the whole system in a matrix, and ask for its range.

B = matrix(QQ, [[f.coefficient(myvar) for myvar in (a, b, c, d)]
    for f in [f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14, f15, f16]])
print(f"B has rank {B.rank()}")

This gives:

B has rank 4

Explicitly, the matrix of the system as built above using a double list comprehension is:

sage: B
[   14  -102   104    24]
[   -7    51   -52   -12]
[  -52   -12  -142  -138]
[   26     6    71    69]
[   28  -204   208    48]
[  -14   102  -104   -24]
[ -104   -24  -284  -276]
[   52    12   142   138]
[  204  -292   -48   176]
[ -102   146    24   -88]
[   24   -88   276  -556]
[  -12    44  -138   278]
[  408  -584   -96   352]
[ -204   292    48  -176]
[   48  -176   552 -1112]
[  -24    88  -276   556]
Preview: (hide)
link

Comments

Thank you very much.

rewi gravatar imagerewi ( 0 years ago )
2

answered 0 years ago

Emmanuel Charpentier gravatar image

@Max Alekseyev has pointed to a general result applicable to your problem, whereas @dan_fulea gives a "manual solution. I want to point out that Sage is able to give you this result. After slightly rearranging your code (I'm lazy) :

Vars=var('a b c d p q r s')
F=[14*a - 102*b + 104*c + 24*d,
   -7*a + 51*b - 52*c - 12*d,
   -52*a - 12*b - 142*c - 138*d,
   26*a + 6*b + 71*c + 69*d,
   28*a - 204*b + 208*c + 48*d ,
   -14*a + 102*b - 104*c - 24*d ,
   -104*a - 24*b - 284*c - 276*d,
   52*a + 12*b + 142*c + 138*d,
   204*a - 292*b - 48*c + 176*d,
   -102*a + 146*b + 24*c - 88*d,
   24*a - 88*b + 276*c - 556*d,
   -12*a + 44*b - 138*c + 278*d ,
   408*a - 584*b - 96*c + 352*d,
   -204*a + 292*b + 48*c - 176*d,
   48*a - 176*b + 552*c - 1112*d,
   -24*a + 88*b - 276*c + 556*d]

one may run :

sage: solve(F,Vars)
[[a == 0, b == 0, c == 0, d == 0, p == r4, q == r3, r == r2, s == r1]]

which tells you that your system as a quadruple infinity of solutions, 'p', 'q, 'r', 's' being undetermined (which is not a surprise, since these variable do not appear in your equations), and the (a, b, c, d) vector having the unique solution (0, 0, 0, 0).

Another way to express this is :

sage: solve(F, (a, b, c, d))
[[a == 0, b == 0, c == 0, d == 0]]

which has the same meaning.

BTW, you can work in Max's direction with :

sage: M=matrix(SR,[[f.coefficient(v) for v in Vars] for f in F]) ; M
[   14  -102   104    24     0     0     0     0]
[   -7    51   -52   -12     0     0     0     0]
[  -52   -12  -142  -138     0     0     0     0]
[   26     6    71    69     0     0     0     0]
[   28  -204   208    48     0     0     0     0]
[  -14   102  -104   -24     0     0     0     0]
[ -104   -24  -284  -276     0     0     0     0]
[   52    12   142   138     0     0     0     0]
[  204  -292   -48   176     0     0     0     0]
[ -102   146    24   -88     0     0     0     0]
[   24   -88   276  -556     0     0     0     0]
[  -12    44  -138   278     0     0     0     0]
[  408  -584   -96   352     0     0     0     0]
[ -204   292    48  -176     0     0     0     0]
[   48  -176   552 -1112     0     0     0     0]
[  -24    88  -276   556     0     0     0     0]
sage: M.rank()
4

Another variant :

sage: MR=matrix(M.columns()[:4]).transpose() ; MR
[   14  -102   104    24]
[   -7    51   -52   -12]
[  -52   -12  -142  -138]
[   26     6    71    69]
[   28  -204   208    48]
[  -14   102  -104   -24]
[ -104   -24  -284  -276]
[   52    12   142   138]
[  204  -292   -48   176]
[ -102   146    24   -88]
[   24   -88   276  -556]
[  -12    44  -138   278]
[  408  -584   -96   352]
[ -204   292    48  -176]
[   48  -176   552 -1112]
[  -24    88  -276   556]
sage: MR.rank()
4

Sage is also able to work out redundant equations, thus avoiding @dan_fulea's manual work :

sage: matrix([r for r in M.echelon_form().rows() if any([v!=0 for v in r])])
[1 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]

Alternatively :

sage: matrix([r for r in MR.echelon_form().rows() if any([v!=0 for v in r])])
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

HTH,

Preview: (hide)
link

Comments

Thank you so much for such a nice code. Thanks

rewi gravatar imagerewi ( 0 years ago )

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 0 years ago

Seen: 64 times

Last updated: Feb 15