Mathematics Asked by Stacey on October 21, 2020
Could someone point me in the right direction as to how to solve:
7a+8b+9c = 1744
I need to know how to do this for other three unknown equations a well so the answer alone won’t help me.
Thanks
The set of integer $a,b,c$ such that $7a+8b+9c=0$ is called a lattice, on this site the tag is integer-lattices. https://math.stackexchange.com/questions/tagged/integer-lattices
Next, we find a basis for the lattice. We do this by applying column operations as multiplication on the right by elementary matrices.
$$ left( begin{array}{rrr} 7&8&9 \ end{array} right) left( begin{array}{rrr} 1&0&0 \ 7&9&-1 \ -7&-8&1 \ end{array} right) = left( begin{array}{rrr} 0&0&1 \ end{array} right) $$
The outcom of doing this is that the $0$ positions in the final row $(0,0,1)$ mark the basis vectors, as columns. So, a basis is
$$ left( begin{array}{rr} 1&0 \ 7&9 \ -7&-8 \ end{array} right) $$ At this stage it is more convenient to write as rows: the entire lattice is parametrized as $$ x(1,7,-7) + y ( 0,9,-8) $$ or $$( x, 7x+9y, -7x-8y) $$
All that remains is to find a single solution for $1744$ and add these. Factoring reveals $1744 = 16 cdot 109 = 8 cdot 218,$ so a fixed solution is $$ ( 0, 218,0) $$
and the set of all solutions is parametrized over the integers as
$$ color{blue}{( x, 218+ 7x+9y, -7x-8y)} $$
If I had to obey inequalities I would define $t = -y$ and write
$$ color{magenta}{( x, 218+ 7x-9t, -7x+8t)} $$ Using these (integer) variables, the non-negative solutions of the original problem occur in the narrow triangle $$ x geq 0, ; ; ; 9t-218 leq 7x leq 8t $$
In this dimension one may calculate a reduced basis by ordinary Gauss reduction of the binary quadratic form. The result is a different parametrization, I should use different letters
$$ color{red}{( -u+4v, 218+ 2u+v, -u-4v)} $$
If ( I cannot tell) you have inequalities (such as all entries non-negative) the first version is probably more convenient, as the $x$ is isolated.
$$ bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc bigcirc $$
Question about the matrix methodology: Column vector $w$ with element gcd = 1. The row is $w^T.$ We have any lattice element $h ; , ; $ meaning $w^T h = 0.$ And we construct a square integer unimodular matrix $W$ with $w^T W = (1,0,0,0...,0).$ This gives $w^T =(1,0,0,...,0) W^{-1}.$ Put together with $w^T h = 0,$ we arrive at $$ (1,0,0,0...0) W^{-1} h = 0. $$ In turn, this means the first element in $W^{-1}h$ is zero, the others are a bunch of integers. so $$ W^{-1} h = left( begin{array}{c} 0 \ g_2 \ g_3 \ vdots \ g_n \ end{array} right) $$ Multiply on the left by $W$ for $$ h = W left( begin{array}{c} 0 \ g_2 \ g_3 \ vdots \ g_n \ end{array} right) $$ If you write this out, you see it means that $h$ itself is an integer linear combination of the columns of $W$ except the first (left hand) column. We get $h = g_2 c_2 + g_3 c_3 + cdots + g_n c_n,$ where $c_j$ is column $j$ in the square matrix $W.$ The second through final columns of $W$ really do span the lattice of integer vectors orthogonal to $w^T.$ Furthermore, $det W = 1$ says that they are independent; the second through $n$th columns of $W$ are a basis.
Answered by Will Jagy on October 21, 2020
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP