System of linear equations - Wikipedia

In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables. Systemoflinearequations FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Severalequationsofdegree1tobesolvedsimultaneously Thisarticleincludesalistofgeneralreferences,butitlackssufficientcorrespondinginlinecitations.Pleasehelptoimprovethisarticlebyintroducingmoreprecisecitations.(October2015)(Learnhowandwhentoremovethistemplatemessage) Inmathematics,asystemoflinearequations(orlinearsystem)isacollectionofoneormorelinearequationsinvolvingthesamevariables.[1][2][3][4][5] AlinearsysteminthreevariablesdeterminesacollectionofplanesTheintersectionpointisthesolution. Forexample, { 3 x + 2 y − z = 1 2 x − 2 y + 4 z = − 2 − x + 1 2 y − z = 0 {\displaystyle{\begin{cases}3x+2y-z=1\\2x-2y+4z=-2\\-x+{\frac{1}{2}}y-z=0\end{cases}}} isasystemofthreeequationsinthethreevariablesx,y,z.Asolutiontoalinearsystemisanassignmentofvaluestothevariablessuchthatalltheequationsaresimultaneouslysatisfied.Asolutiontothesystemaboveisgivenbythefollowingorderedtriple. ( x , y , z ) = ( 1 , − 2 , − 2 ) {\displaystyle(x,y,z)=(1,-2,-2)} sinceitmakesallthreeequationsvalid.Theword"system"indicatesthattheequationsaretobeconsideredcollectively,ratherthanindividually. Inmathematics,thetheoryoflinearsystemsisthebasisandafundamentalpartoflinearalgebra,asubjectwhichisusedinmostpartsofmodernmathematics.Computationalalgorithmsforfindingthesolutionsareanimportantpartofnumericallinearalgebra,andplayaprominentroleinengineering,physics,chemistry,computerscience,andeconomics.Asystemofnon-linearequationscanoftenbeapproximatedbyalinearsystem(seelinearization),ahelpfultechniquewhenmakingamathematicalmodelorcomputersimulationofarelativelycomplexsystem. Veryoften,thecoefficientsoftheequationsarerealorcomplexnumbersandthesolutionsaresearchedinthesamesetofnumbers,butthetheoryandthealgorithmsapplyforcoefficientsandsolutionsinanyfield.Forsolutionsinanintegraldomainliketheringoftheintegers,orinotheralgebraicstructures,othertheorieshavebeendeveloped,seeLinearequationoveraring.Integerlinearprogrammingisacollectionofmethodsforfindingthe"best"integersolution(whentherearemany).Gröbnerbasistheoryprovidesalgorithmswhencoefficientsandunknownsarepolynomials.Alsotropicalgeometryisanexampleoflinearalgebrainamoreexoticstructure. Contents 1Elementaryexamples 1.1Trivialexample 1.2Simplenontrivialexample 2Generalform 2.1Vectorequation 2.2Matrixequation 3Solutionset 3.1Geometricinterpretation 3.2Generalbehavior 4Properties 4.1Independence 4.2Consistency 4.3Equivalence 5Solvingalinearsystem 5.1Describingthesolution 5.2Eliminationofvariables 5.3Rowreduction 5.4Cramer'srule 5.5Matrixsolution 5.6Othermethods 6Homogeneoussystems 6.1Homogeneoussolutionset 6.2Relationtononhomogeneoussystems 7Seealso 8Notes 9References 10Furtherreading 11Externallinks Elementaryexamples[edit] Trivialexample[edit] Thesystemofoneequationinoneunknown 2 x = 4 {\displaystyle2x=4} hasthesolution x = 2. {\displaystylex=2.} However,alinearsystemiscommonlyconsideredashavingatleasttwoequations. Simplenontrivialexample[edit] Thesimplestkindofnontriviallinearsysteminvolvestwoequationsandtwovariables: 2 x + 3 y = 6 4 x + 9 y = 15 . {\displaystyle{\begin{alignedat}{5}2x&&\;+\;&&3y&&\;=\;&&6&\\4x&&\;+\;&&9y&&\;=\;&&15&.\end{alignedat}}} Onemethodforsolvingsuchasystemisasfollows.First,solvethetopequationfor x {\displaystylex} intermsof y {\displaystyley} : x = 3 − 3 2 y . {\displaystylex=3-{\frac{3}{2}}y.} Nowsubstitutethisexpressionforxintothebottomequation: 4 ( 3 − 3 2 y ) + 9 y = 15. {\displaystyle4\left(3-{\frac{3}{2}}y\right)+9y=15.} Thisresultsinasingleequationinvolvingonlythevariable y {\displaystyley} .Solvinggives y = 1 {\displaystyley=1} ,andsubstitutingthisbackintotheequationfor x {\displaystylex} yields x = 3 / 2 {\displaystylex=3/2} .Thismethodgeneralizestosystemswithadditionalvariables(see"eliminationofvariables"below,orthearticleonelementaryalgebra.) Generalform[edit] Ageneralsystemofmlinearequationswithnunknownsandcoefficientscanbewrittenas { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n + b 1 = 0 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n + b 2 = 0 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n + b m = 0 , {\displaystyle{\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\dots+a_{1n}x_{n}+b_{1}=0\\a_{21}x_{1}+a_{22}x_{2}+\dots+a_{2n}x_{n}+b_{2}=0\\\vdots\\a_{m1}x_{1}+a_{m2}x_{2}+\dots+a_{mn}x_{n}+b_{m}=0,\end{cases}}} where x 1 , x 2 , … , x n {\displaystylex_{1},x_{2},\dots,x_{n}} aretheunknowns, a 11 , a 12 , … , a m n {\displaystylea_{11},a_{12},\dots,a_{mn}} arethecoefficientsofthesystemsuchthat a 11 + a 12 + ⋯ + a m n ≠ 0 {\displaystylea_{11}+a_{12}+\dots+a_{mn}\neq0} ,and b 1 , b 2 , … , b m {\displaystyleb_{1},b_{2},\dots,b_{m}} aretheconstantterms. Oftenthecoefficientsandunknownsarerealorcomplexnumbers,butintegersandrationalnumbersarealsoseen,asarepolynomialsandelementsofanabstractalgebraicstructure. Vectorequation[edit] Oneextremelyhelpfulviewisthateachunknownisaweightforacolumnvectorinalinearcombination. x 1 [ a 11 a 21 ⋮ a m 1 ] + x 2 [ a 12 a 22 ⋮ a m 2 ] + ⋯ + x n [ a 1 n a 2 n ⋮ a m n ] + [ b 1 b 2 ⋮ b m ] = 0 {\displaystylex_{1}{\begin{bmatrix}a_{11}\\a_{21}\\\vdots\\a_{m1}\end{bmatrix}}+x_{2}{\begin{bmatrix}a_{12}\\a_{22}\\\vdots\\a_{m2}\end{bmatrix}}+\dots+x_{n}{\begin{bmatrix}a_{1n}\\a_{2n}\\\vdots\\a_{mn}\end{bmatrix}}+{\begin{bmatrix}b_{1}\\b_{2}\\\vdots\\b_{m}\end{bmatrix}}=0} Thisallowsallthelanguageandtheoryofvectorspaces(ormoregenerally,modules)tobebroughttobear.Forexample,thecollectionofallpossiblelinearcombinationsofthevectorsontheleft-handsideiscalledtheirspan,andtheequationshaveasolutionjustwhentheright-handvectoriswithinthatspan.Ifeveryvectorwithinthatspanhasexactlyoneexpressionasalinearcombinationofthegivenleft-handvectors,thenanysolutionisunique.Inanyevent,thespanhasabasisoflinearlyindependentvectorsthatdoguaranteeexactlyoneexpression;andthenumberofvectorsinthatbasis(itsdimension)cannotbelargerthanmorn,butitcanbesmaller.Thisisimportantbecauseifwehavemindependentvectorsasolutionisguaranteedregardlessoftheright-handside,andotherwisenotguaranteed. Matrixequation[edit] Thevectorequationisequivalenttoamatrixequationoftheform A x = b {\displaystyleA\mathbf{x}=\mathbf{b}} whereAisanm×nmatrix,xisacolumnvectorwithnentries,andbisacolumnvectorwithmentries. A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] , x = [ x 1 x 2 ⋮ x n ] , b = [ b 1 b 2 ⋮ b m ] {\displaystyleA={\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&\ddots&\vdots\\a_{m1}&a_{m2}&\cdots&a_{mn}\end{bmatrix}},\quad\mathbf{x}={\begin{bmatrix}x_{1}\\x_{2}\\\vdots\\x_{n}\end{bmatrix}},\quad\mathbf{b}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots\\b_{m}\end{bmatrix}}} Thenumberofvectorsinabasisforthespanisnowexpressedastherankofthematrix. Solutionset[edit] Thesolutionsetfortheequationsx−y=−1and3x+y=9isthesinglepoint(2, 3). Asolutionofalinearsystemisanassignmentofvaluestothevariablesx1,x2,...,xnsuchthateachoftheequationsissatisfied.Thesetofallpossiblesolutionsiscalledthesolutionset. Alinearsystemmaybehaveinanyoneofthreepossibleways: Thesystemhasinfinitelymanysolutions. Thesystemhasasingleuniquesolution. Thesystemhasnosolution. Geometricinterpretation[edit] Forasysteminvolvingtwovariables(xandy),eachlinearequationdeterminesalineonthexy-plane.Becauseasolutiontoalinearsystemmustsatisfyalloftheequations,thesolutionsetistheintersectionoftheselines,andishenceeitheraline,asinglepoint,ortheemptyset. Forthreevariables,eachlinearequationdeterminesaplaneinthree-dimensionalspace,andthesolutionsetistheintersectionoftheseplanes.Thusthesolutionsetmaybeaplane,aline,asinglepoint,ortheemptyset.Forexample,asthreeparallelplanesdonothaveacommonpoint,thesolutionsetoftheirequationsisempty;thesolutionsetoftheequationsofthreeplanesintersectingatapointissinglepoint;ifthreeplanespassthroughtwopoints,theirequationshaveatleasttwocommonsolutions;infactthesolutionsetisinfiniteandconsistsinallthelinepassingthroughthesepoints.[6] Fornvariables,eachlinearequationdeterminesahyperplaneinn-dimensionalspace.Thesolutionsetistheintersectionofthesehyperplanes,andisaflat,whichmayhaveanydimensionlowerthann. Generalbehavior[edit] Thesolutionsetfortwoequationsinthreevariablesis,ingeneral,aline. Ingeneral,thebehaviorofalinearsystemisdeterminedbytherelationshipbetweenthenumberofequationsandthenumberofunknowns.Here,"ingeneral"meansthatadifferentbehaviormayoccurforspecificvaluesofthecoefficientsoftheequations. Ingeneral,asystemwithfewerequationsthanunknownshasinfinitelymanysolutions,butitmayhavenosolution.Suchasystemisknownasanunderdeterminedsystem. Ingeneral,asystemwiththesamenumberofequationsandunknownshasasingleuniquesolution. Ingeneral,asystemwithmoreequationsthanunknownshasnosolution.Suchasystemisalsoknownasanoverdeterminedsystem. Inthefirstcase,thedimensionofthesolutionsetis,ingeneral,equalton−m,wherenisthenumberofvariablesandmisthenumberofequations. Thefollowingpicturesillustratethistrichotomyinthecaseoftwovariables: Oneequation Twoequations Threeequations Thefirstsystemhasinfinitelymanysolutions,namelyallofthepointsontheblueline.Thesecondsystemhasasingleuniquesolution,namelytheintersectionofthetwolines.Thethirdsystemhasnosolutions,sincethethreelinessharenocommonpoint. Itmustbekeptinmindthatthepicturesaboveshowonlythemostcommoncase(thegeneralcase).Itispossibleforasystemoftwoequationsandtwounknownstohavenosolution(ifthetwolinesareparallel),orforasystemofthreeequationsandtwounknownstobesolvable(ifthethreelinesintersectatasinglepoint). Asystemoflinearequationsbehavedifferentlyfromthegeneralcaseiftheequationsarelinearlydependent,orifitisinconsistentandhasnomoreequationsthanunknowns. Properties[edit] Independence[edit] Theequationsofalinearsystemareindependentifnoneoftheequationscanbederivedalgebraicallyfromtheothers.Whentheequationsareindependent,eachequationcontainsnewinformationaboutthevariables,andremovinganyoftheequationsincreasesthesizeofthesolutionset.Forlinearequations,logicalindependenceisthesameaslinearindependence. Theequationsx−2y=−1,3x+5y=8,and4x+3y=7arelinearlydependent. Forexample,theequations 3 x + 2 y = 6 and 6 x + 4 y = 12 {\displaystyle3x+2y=6\;\;\;\;{\text{and}}\;\;\;\;6x+4y=12} arenotindependent—theyarethesameequationwhenscaledbyafactoroftwo,andtheywouldproduceidenticalgraphs.Thisisanexampleofequivalenceinasystemoflinearequations. Foramorecomplicatedexample,theequations x − 2 y = − 1 3 x + 5 y = 8 4 x + 3 y = 7 {\displaystyle{\begin{alignedat}{5}x&&\;-\;&&2y&&\;=\;&&-1&\\3x&&\;+\;&&5y&&\;=\;&&8&\\4x&&\;+\;&&3y&&\;=\;&&7&\end{alignedat}}} arenotindependent,becausethethirdequationisthesumoftheothertwo.Indeed,anyoneoftheseequationscanbederivedfromtheothertwo,andanyoneoftheequationscanberemovedwithoutaffectingthesolutionset.Thegraphsoftheseequationsarethreelinesthatintersectatasinglepoint. Consistency[edit] Seealso:Consistentandinconsistentequations Theequations3x+2y=6and3x+2y=12areinconsistent. Alinearsystemisinconsistentifithasnosolution,andotherwiseitissaidtobeconsistent.Whenthesystemisinconsistent,itispossibletoderiveacontradictionfromtheequations,thatmayalwaysberewrittenasthestatement0=1. Forexample,theequations 3 x + 2 y = 6 and 3 x + 2 y = 12 {\displaystyle3x+2y=6\;\;\;\;{\text{and}}\;\;\;\;3x+2y=12} areinconsistent.Infact,bysubtractingthefirstequationfromthesecondoneandmultiplyingbothsidesoftheresultby1/6,weget0=1.Thegraphsoftheseequationsonthexy-planeareapairofparallellines. Itispossibleforthreelinearequationstobeinconsistent,eventhoughanytwoofthemareconsistenttogether.Forexample,theequations x + y = 1 2 x + y = 1 3 x + 2 y = 3 {\displaystyle{\begin{alignedat}{7}x&&\;+\;&&y&&\;=\;&&1&\\2x&&\;+\;&&y&&\;=\;&&1&\\3x&&\;+\;&&2y&&\;=\;&&3&\end{alignedat}}} areinconsistent.Addingthefirsttwoequationstogethergives3x+2y=2,whichcanbesubtractedfromthethirdequationtoyield0=1.Anytwooftheseequationshaveacommonsolution.Thesamephenomenoncanoccurforanynumberofequations. Ingeneral,inconsistenciesoccuriftheleft-handsidesoftheequationsinasystemarelinearlydependent,andtheconstanttermsdonotsatisfythedependencerelation.Asystemofequationswhoseleft-handsidesarelinearlyindependentisalwaysconsistent. Puttingitanotherway,accordingtotheRouché–Capellitheorem,anysystemofequations(overdeterminedorotherwise)isinconsistentiftherankoftheaugmentedmatrixisgreaterthantherankofthecoefficientmatrix.If,ontheotherhand,theranksofthesetwomatricesareequal,thesystemmusthaveatleastonesolution.Thesolutionisuniqueifandonlyiftherankequalsthenumberofvariables.Otherwisethegeneralsolutionhaskfreeparameterswherekisthedifferencebetweenthenumberofvariablesandtherank;henceinsuchacasethereareaninfinitudeofsolutions.Therankofasystemofequations(i.e.therankoftheaugmentedmatrix)canneverbehigherthan[thenumberofvariables]+1,whichmeansthatasystemwithanynumberofequationscanalwaysbereducedtoasystemthathasanumberofindependentequationsthatisatmostequalto[thenumberofvariables]+1. Equivalence[edit] Twolinearsystemsusingthesamesetofvariablesareequivalentifeachoftheequationsinthesecondsystemcanbederivedalgebraicallyfromtheequationsinthefirstsystem,andviceversa.Twosystemsareequivalentifeitherbothareinconsistentoreachequationofeachofthemisalinearcombinationoftheequationsoftheotherone.Itfollowsthattwolinearsystemsareequivalentifandonlyiftheyhavethesamesolutionset. Solvingalinearsystem[edit] Thereareseveralalgorithmsforsolvingasystemoflinearequations. Describingthesolution[edit] Whenthesolutionsetisfinite,itisreducedtoasingleelement.Inthiscase,theuniquesolutionisdescribedbyasequenceofequationswhoseleft-handsidesarethenamesoftheunknownsandright-handsidesarethecorrespondingvalues,forexample ( x = 3 , y = − 2 , z = 6 ) {\displaystyle(x=3,\;y=-2,\;z=6)} .Whenanorderontheunknownshasbeenfixed,forexamplethealphabeticalorderthesolutionmaybedescribedasavectorofvalues,like ( 3 , − 2 , 6 ) {\displaystyle(3,\,-2,\,6)} forthepreviousexample. Todescribeasetwithaninfinitenumberofsolutions,typicallysomeofthevariablesaredesignatedasfree(orindependent,orasparameters),meaningthattheyareallowedtotakeanyvalue,whiletheremainingvariablesaredependentonthevaluesofthefreevariables. Forexample,considerthefollowingsystem: x + 3 y − 2 z = 5 3 x + 5 y + 6 z = 7 {\displaystyle{\begin{alignedat}{7}x&&\;+\;&&3y&&\;-\;&&2z&&\;=\;&&5&\\3x&&\;+\;&&5y&&\;+\;&&6z&&\;=\;&&7&\end{alignedat}}} Thesolutionsettothissystemcanbedescribedbythefollowingequations: x = − 7 z − 1 and y = 3 z + 2 . {\displaystylex=-7z-1\;\;\;\;{\text{and}}\;\;\;\;y=3z+2{\text{.}}} Herezisthefreevariable,whilexandyaredependentonz.Anypointinthesolutionsetcanbeobtainedbyfirstchoosingavalueforz,andthencomputingthecorrespondingvaluesforxandy. Eachfreevariablegivesthesolutionspaceonedegreeoffreedom,thenumberofwhichisequaltothedimensionofthesolutionset.Forexample,thesolutionsetfortheaboveequationisaline,sinceapointinthesolutionsetcanbechosenbyspecifyingthevalueoftheparameterz.Aninfinitesolutionofhigherordermaydescribeaplane,orhigher-dimensionalset. Differentchoicesforthefreevariablesmayleadtodifferentdescriptionsofthesamesolutionset.Forexample,thesolutiontotheaboveequationscanalternativelybedescribedasfollows: y = − 3 7 x + 11 7 and z = − 1 7 x − 1 7 . {\displaystyley=-{\frac{3}{7}}x+{\frac{11}{7}}\;\;\;\;{\text{and}}\;\;\;\;z=-{\frac{1}{7}}x-{\frac{1}{7}}{\text{.}}} Herexisthefreevariable,andyandzaredependent. Eliminationofvariables[edit] Thesimplestmethodforsolvingasystemoflinearequationsistorepeatedlyeliminatevariables.Thismethodcanbedescribedasfollows: Inthefirstequation,solveforoneofthevariablesintermsoftheothers. Substitutethisexpressionintotheremainingequations.Thisyieldsasystemofequationswithonefewerequationandunknown. Repeatsteps1and2untilthesystemisreducedtoasinglelinearequation. Solvethisequation,andthenback-substituteuntiltheentiresolutionisfound. Forexample,considerthefollowingsystem: { x + 3 y − 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle{\begin{cases}x+3y-2z=5\\3x+5y+6z=7\\2x+4y+3z=8\end{cases}}} Solvingthefirstequationforxgivesx=5+2z-3y,andpluggingthisintothesecondandthirdequationyields { y = 3 z + 2 y = 7 2 z + 1 {\displaystyle{\begin{cases}y=3z+2\\y={\tfrac{7}{2}}z+1\end{cases}}} SincetheLHSofbothoftheseequationsequaly,equatingtheRHSoftheequations.Wenowhave: 3 z + 2 = 7 2 z + 1 ⇒ z = 2 {\displaystyle{\begin{aligned}3z+2={\tfrac{7}{2}}z+1\\\Rightarrowz=2\end{aligned}}} Substitutingz=2intothesecondorthirdequationgivesy=8,andthevaluesofyandzintothefirstequationyieldsx=−15.Therefore,thesolutionsetistheorderedtriple ( x , y , z ) = ( − 15 , 8 , 2 ) {\displaystyle(x,y,z)=(-15,8,2)} . Rowreduction[edit] Mainarticle:Gaussianelimination Inrowreduction(alsoknownasGaussianelimination),thelinearsystemisrepresentedasanaugmentedmatrix: [ 1 3 − 2 5 3 5 6 7 2 4 3 8 ] . {\displaystyle\left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]{\text{.}}} Thismatrixisthenmodifiedusingelementaryrowoperationsuntilitreachesreducedrowechelonform.Therearethreetypesofelementaryrowoperations: Type1:Swapthepositionsoftworows. Type2:Multiplyarowbyanonzeroscalar. Type3:Addtoonerowascalarmultipleofanother. Becausetheseoperationsarereversible,theaugmentedmatrixproducedalwaysrepresentsalinearsystemthatisequivalenttotheoriginal. Thereareseveralspecificalgorithmstorow-reduceanaugmentedmatrix,thesimplestofwhichareGaussianeliminationandGauss–Jordanelimination.ThefollowingcomputationshowsGauss–Jordaneliminationappliedtothematrixabove: [ 1 3 − 2 5 3 5 6 7 2 4 3 8 ] ∼ [ 1 3 − 2 5 0 − 4 12 − 8 2 4 3 8 ] ∼ [ 1 3 − 2 5 0 − 4 12 − 8 0 − 2 7 − 2 ] ∼ [ 1 3 − 2 5 0 1 − 3 2 0 − 2 7 − 2 ] ∼ [ 1 3 − 2 5 0 1 − 3 2 0 0 1 2 ] ∼ [ 1 3 − 2 5 0 1 0 8 0 0 1 2 ] ∼ [ 1 3 0 9 0 1 0 8 0 0 1 2 ] ∼ [ 1 0 0 − 15 0 1 0 8 0 0 1 2 ] . {\displaystyle{\begin{aligned}\left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]&\sim\left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\2&4&3&8\end{array}}\right]\sim\left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\0&-2&7&-2\end{array}}\right]\sim\left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&-2&7&-2\end{array}}\right]\\&\sim\left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&0&1&2\end{array}}\right]\sim\left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim\left[{\begin{array}{rrr|r}1&3&0&9\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim\left[{\begin{array}{rrr|r}1&0&0&-15\\0&1&0&8\\0&0&1&2\end{array}}\right].\end{aligned}}} Thelastmatrixisinreducedrowechelonform,andrepresentsthesystemx=−15,y=8,z=2.Acomparisonwiththeexampleintheprevioussectiononthealgebraiceliminationofvariablesshowsthatthesetwomethodsareinfactthesame;thedifferenceliesinhowthecomputationsarewrittendown. Cramer'srule[edit] Mainarticle:Cramer'srule Cramer'sruleisanexplicitformulaforthesolutionofasystemoflinearequations,witheachvariablegivenbyaquotientoftwodeterminants.Forexample,thesolutiontothesystem x + 3 y − 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle{\begin{alignedat}{7}x&\;+&\;3y&\;-&\;2z&\;=&\;5\\3x&\;+&\;5y&\;+&\;6z&\;=&\;7\\2x&\;+&\;4y&\;+&\;3z&\;=&\;8\end{alignedat}}} isgivenby x = | 5 3 − 2 7 5 6 8 4 3 | | 1 3 − 2 3 5 6 2 4 3 | , y = | 1 5 − 2 3 7 6 2 8 3 | | 1 3 − 2 3 5 6 2 4 3 | , z = | 1 3 5 3 5 7 2 4 8 | | 1 3 − 2 3 5 6 2 4 3 | . {\displaystylex={\frac{\,{\begin{vmatrix}5&3&-2\\7&5&6\\8&4&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;y={\frac{\,{\begin{vmatrix}1&5&-2\\3&7&6\\2&8&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;z={\frac{\,{\begin{vmatrix}1&3&5\\3&5&7\\2&4&8\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}}.} Foreachvariable,thedenominatoristhedeterminantofthematrixofcoefficients,whilethenumeratoristhedeterminantofamatrixinwhichonecolumnhasbeenreplacedbythevectorofconstantterms. ThoughCramer'sruleisimportanttheoretically,ithaslittlepracticalvalueforlargematrices,sincethecomputationoflargedeterminantsissomewhatcumbersome.(Indeed,largedeterminantsaremosteasilycomputedusingrowreduction.) Further,Cramer'srulehasverypoornumericalproperties,makingitunsuitableforsolvingevensmallsystemsreliably,unlesstheoperationsareperformedinrationalarithmeticwithunboundedprecision.[citationneeded] Matrixsolution[edit] Iftheequationsystemisexpressedinthematrixform A x = b {\displaystyleA\mathbf{x}=\mathbf{b}} ,theentiresolutionsetcanalsobeexpressedinmatrixform.IfthematrixAissquare(hasmrowsandn=mcolumns)andhasfullrank(allmrowsareindependent),thenthesystemhasauniquesolutiongivenby x = A − 1 b {\displaystyle\mathbf{x}=A^{-1}\mathbf{b}} where A − 1 {\displaystyleA^{-1}} istheinverseofA.Moregenerally,regardlessofwhetherm=nornotandregardlessoftherankofA,allsolutions(ifanyexist)aregivenusingtheMoore–PenroseinverseofA,denoted A + {\displaystyleA^{+}} ,asfollows: x = A + b + ( I − A + A ) w {\displaystyle\mathbf{x}=A^{+}\mathbf{b}+\left(I-A^{+}A\right)\mathbf{w}} where w {\displaystyle\mathbf{w}} isavectoroffreeparametersthatrangesoverallpossiblen×1vectors.Anecessaryandsufficientconditionforanysolution(s)toexististhatthepotentialsolutionobtainedusing w = 0 {\displaystyle\mathbf{w}=\mathbf{0}} satisfy A x = b {\displaystyleA\mathbf{x}=\mathbf{b}} —thatis,that A A + b = b . {\displaystyleAA^{+}\mathbf{b}=\mathbf{b}.} Ifthisconditiondoesnothold,theequationsystemisinconsistentandhasnosolution.Iftheconditionholds,thesystemisconsistentandatleastonesolutionexists.Forexample,intheabove-mentionedcaseinwhichAissquareandoffullrank, A + {\displaystyleA^{+}} simplyequals A − 1 {\displaystyleA^{-1}} andthegeneralsolutionequationsimplifiesto x = A − 1 b + ( I − A − 1 A ) w = A − 1 b + ( I − I ) w = A − 1 b {\displaystyle\mathbf{x}=A^{-1}\mathbf{b}+\left(I-A^{-1}A\right)\mathbf{w}=A^{-1}\mathbf{b}+\left(I-I\right)\mathbf{w}=A^{-1}\mathbf{b}} aspreviouslystated,where w {\displaystyle\mathbf{w}} hascompletelydroppedoutofthesolution,leavingonlyasinglesolution.Inothercases,though, w {\displaystyle\mathbf{w}} remainsandhenceaninfinitudeofpotentialvaluesofthefreeparametervector w {\displaystyle\mathbf{w}} giveaninfinitudeofsolutionsoftheequation. Othermethods[edit] Whilesystemsofthreeorfourequationscanbereadilysolvedbyhand(seeCracovian),computersareoftenusedforlargersystems.ThestandardalgorithmforsolvingasystemoflinearequationsisbasedonGaussianeliminationwithsomemodifications.Firstly,itisessentialtoavoiddivisionbysmallnumbers,whichmayleadtoinaccurateresults.Thiscanbedonebyreorderingtheequationsifnecessary,aprocessknownaspivoting.Secondly,thealgorithmdoesnotexactlydoGaussianelimination,butitcomputestheLUdecompositionofthematrixA.Thisismostlyanorganizationaltool,butitismuchquickerifonehastosolveseveralsystemswiththesamematrixAbutdifferentvectorsb. IfthematrixAhassomespecialstructure,thiscanbeexploitedtoobtainfasterormoreaccuratealgorithms.Forinstance,systemswithasymmetricpositivedefinitematrixcanbesolvedtwiceasfastwiththeCholeskydecomposition.LevinsonrecursionisafastmethodforToeplitzmatrices.Specialmethodsexistalsoformatriceswithmanyzeroelements(so-calledsparsematrices),whichappearofteninapplications. Acompletelydifferentapproachisoftentakenforverylargesystems,whichwouldotherwisetaketoomuchtimeormemory.Theideaistostartwithaninitialapproximationtothesolution(whichdoesnothavetobeaccurateatall),andtochangethisapproximationinseveralstepstobringitclosertothetruesolution.Oncetheapproximationissufficientlyaccurate,thisistakentobethesolutiontothesystem.Thisleadstotheclassofiterativemethods.Forsomesparsematrices,theintroductionofrandomnessimprovesthespeedoftheiterativemethods.[7] Thereisalsoaquantumalgorithmforlinearsystemsofequations.[8] Homogeneoussystems[edit] Seealso:Homogeneousdifferentialequation Asystemoflinearequationsishomogeneousifalloftheconstanttermsarezero: a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = 0 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = 0 ⋮   a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = 0. {\displaystyle{\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots+\;&&a_{1n}x_{n}&&\;=\;&&&0\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots+\;&&a_{2n}x_{n}&&\;=\;&&&0\\&&&&&&&&&&\vdots\;\&&&\\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots+\;&&a_{mn}x_{n}&&\;=\;&&&0.\\\end{alignedat}}} Ahomogeneoussystemisequivalenttoamatrixequationoftheform A x = 0 {\displaystyleA\mathbf{x}=\mathbf{0}} whereAisanm×nmatrix,xisacolumnvectorwithnentries,and0isthezerovectorwithmentries. Homogeneoussolutionset[edit] Everyhomogeneoussystemhasatleastonesolution,knownasthezero(ortrivial)solution,whichisobtainedbyassigningthevalueofzerotoeachofthevariables.Ifthesystemhasanon-singularmatrix(det(A)≠0)thenitisalsotheonlysolution.Ifthesystemhasasingularmatrixthenthereisasolutionsetwithaninfinitenumberofsolutions.Thissolutionsethasthefollowingadditionalproperties: Ifuandvaretwovectorsrepresentingsolutionstoahomogeneoussystem,thenthevectorsumu+visalsoasolutiontothesystem. Ifuisavectorrepresentingasolutiontoahomogeneoussystem,andrisanyscalar,thenruisalsoasolutiontothesystem. TheseareexactlythepropertiesrequiredforthesolutionsettobealinearsubspaceofRn.Inparticular,thesolutionsettoahomogeneoussystemisthesameasthenullspaceofthecorrespondingmatrixA. Numericalsolutionstoahomogeneoussystemcanbefoundwithasingularvaluedecomposition. Relationtononhomogeneoussystems[edit] Thereisacloserelationshipbetweenthesolutionstoalinearsystemandthesolutionstothecorrespondinghomogeneoussystem: A x = b and A x = 0 . {\displaystyleA\mathbf{x}=\mathbf{b}\qquad{\text{and}}\qquadA\mathbf{x}=\mathbf{0}.} Specifically,ifpisanyspecificsolutiontothelinearsystemAx=b,thentheentiresolutionsetcanbedescribedas { p + v : v  isanysolutionto  A x = 0 } . {\displaystyle\left\{\mathbf{p}+\mathbf{v}:\mathbf{v}{\text{isanysolutionto}}A\mathbf{x}=\mathbf{0}\right\}.} Geometrically,thissaysthatthesolutionsetforAx=bisatranslationofthesolutionsetforAx=0.Specifically,theflatforthefirstsystemcanbeobtainedbytranslatingthelinearsubspaceforthehomogeneoussystembythevectorp. ThisreasoningonlyappliesifthesystemAx=bhasatleastonesolution.ThisoccursifandonlyifthevectorbliesintheimageofthelineartransformationA. Seealso[edit] Arrangementofhyperplanes Iterativerefinement Coatesgraph LAPACK(thefreestandardpackagetosolvelinearequationsnumerically;availableinFortran,C,C++) Linearequationoveraring Linearleastsquares Matrixdecomposition Matrixsplitting NAGNumericalLibrary(NAGLibraryversionsofLAPACKsolvers) RybickiPressalgorithm Simultaneousequations Notes[edit] ^Anton(1987,p. 2) ^Beauregard&Fraleigh(1973,p. 65) ^Burden&Faires(1993,p. 324) ^Golub&VanLoan(1996,p. 87) ^Harper(1976,p. 57) ^CharlesG.Cullen(1990).MatricesandLinearTransformations.MA:Dover.p. 3.ISBN 978-0-486-66328-9. ^Hartnett,Kevin(8March2021)."NewAlgorithmBreaksSpeedLimitforSolvingLinearEquations".QuantaMagazine.Retrieved9March2021. ^Quantumalgorithmforsolvinglinearsystemsofequations,byHarrowetal.. References[edit] Anton,Howard(1987),ElementaryLinearAlgebra(5th ed.),NewYork:Wiley,ISBN 0-471-84819-0 Beauregard,RaymondA.;Fraleigh,JohnB.(1973),AFirstCourseInLinearAlgebra:withOptionalIntroductiontoGroups,Rings,andFields,Boston:HoughtonMifflinCompany,ISBN 0-395-14017-X Burden,RichardL.;Faires,J.Douglas(1993),NumericalAnalysis(5th ed.),Boston:Prindle,WeberandSchmidt,ISBN 0-534-93219-3 Golub,GeneH.;VanLoan,CharlesF.(1996),MatrixComputations(3rd ed.),Baltimore:JohnsHopkinsUniversityPress,ISBN 0-8018-5414-8 Harper,Charlie(1976),IntroductiontoMathematicalPhysics,NewJersey:Prentice-Hall,ISBN 0-13-487538-9 Furtherreading[edit] Axler,SheldonJay(1997),LinearAlgebraDoneRight(2nd ed.),Springer-Verlag,ISBN 0-387-98259-0 Lay,DavidC.(August22,2005),LinearAlgebraandItsApplications(3rd ed.),AddisonWesley,ISBN 978-0-321-28713-7 Meyer,CarlD.(February15,2001),MatrixAnalysisandAppliedLinearAlgebra,SocietyforIndustrialandAppliedMathematics(SIAM),ISBN 978-0-89871-454-8,archivedfromtheoriginalonMarch1,2001 Poole,David(2006),LinearAlgebra:AModernIntroduction(2nd ed.),Brooks/Cole,ISBN 0-534-99845-3 Anton,Howard(2005),ElementaryLinearAlgebra(ApplicationsVersion)(9th ed.),WileyInternational Leon,StevenJ.(2006),LinearAlgebraWithApplications(7th ed.),PearsonPrenticeHall Strang,Gilbert(2005),LinearAlgebraandItsApplications Externallinks[edit] MediarelatedtoSystemoflinearequationsatWikimediaCommons vteLinearalgebraBasicconcepts Scalar Vector Vectorspace Scalarmultiplication Vectorprojection Linearspan Linearmap Linearprojection Linearindependence Linearcombination Basis Changeofbasis Rowandcolumnvectors Rowandcolumnspaces Kernel Eigenvaluesandeigenvectors Transpose Linearequations Matrices Block Decomposition Invertible Minor Multiplication Rank Transformation Cramer'srule Gaussianelimination Bilinear Orthogonality Dotproduct Innerproductspace Outerproduct Kroneckerproduct Gram–Schmidtprocess Multilinearalgebra Determinant Crossproduct Tripleproduct Seven-dimensionalcrossproduct Geometricalgebra Exterioralgebra Bivector Multivector Tensor Outermorphism Vectorspaceconstructions Dual Directsum Functionspace Quotient Subspace Tensorproduct Numerical Floating-point Numericalstability BasicLinearAlgebraSubprograms Sparsematrix Comparisonoflinearalgebralibraries Category Outline Mathematicsportal Authoritycontrol:Nationallibraries Germany Retrievedfrom"https://en.wikipedia.org/w/index.php?title=System_of_linear_equations&oldid=1111724814" Categories:EquationsLinearalgebraNumericallinearalgebraHiddencategories:ArticleswithshortdescriptionShortdescriptionisdifferentfromWikidataArticleslackingin-textcitationsfromOctober2015Allarticleslackingin-textcitationsAllarticleswithunsourcedstatementsArticleswithunsourcedstatementsfromMarch2017CommonscategorylinkfromWikidataArticleswithGNDidentifiers Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk English Views ReadEditViewhistory More Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Inotherprojects WikimediaCommons Languages AlemannischالعربيةAragonésAsturianuAzərbaycancaБашҡортсаБеларускаяБеларуская(тарашкевіца)БългарскиBosanskiCatalàЧӑвашлаČeštinaDeutschEestiΕλληνικάEspañolEsperantoEuskaraفارسیFijiHindiFrançaisGalego한국어Հայերենहिन्दीHrvatskiBahasaIndonesiaInterlinguaÍslenskaItalianoעבריתLatinaLatviešuLombardMagyarМакедонскиBahasaMelayuNederlands日本語NorskbokmålNorsknynorskOccitanਪੰਜਾਬੀپنجابیPolskiPortuguêsRomânăРусскийසිංහලSimpleEnglishسنڌيSlovenčinaSlovenščinaکوردیСрпски/srpskiSrpskohrvatski/српскохрватскиSuomiSvenskaதமிழ்Татарча/tatarçaไทยTürkçeУкраїнськаاردوTiếngViệtWinaray吴语粵語中文 Editlinks