Lecture 25: Exact Linear Algebra

 

Linear algebra is the study of matrices, vectors, solving linear systems of equations, vector spaces, and linear transformation.    It is a topic that is loaded with interesting algorithms, and Sage is good at it.    In this section, we will focus on exact linear algebra, in which all matrices and vectors that we consider have exact entries (e.g., rationals, numbers modulo $p$, polynomials, etc.), as opposed to numerical linear algebra; thus, for us, roundoff error and general numerical analysis are not relevant. 

{{{id=5| /// }}}

Documentation for Linear Algebra in Sage

Quick Reference Card:  Available at http://wiki.sagemath.org/quickref

Relevant sections of the Sage reference manual: 

Robert Beezer's Free Open Source Undergraduate Linear Algebra Book:  http://linear.ups.edu/

{{{id=8| /// }}}

Underlying Technology

{{{id=7| /// }}}

Matrices and Vectors

Arithmetic with Matrices

{{{id=69| A = matrix(QQ, 3, 4, [1..12]); B = matrix(QQ, 4,2, [1..8]) show( (A,B) ) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rrrr} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{array}\right), \left(\begin{array}{rr} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ 7 & 8 \end{array}\right)\right)
}}} {{{id=68| show(A*B) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rr} 50 & 60 \\ 114 & 140 \\ 178 & 220 \end{array}\right)
}}}

Errors, since mathematically this makes no sense:

{{{id=77| A + B /// Traceback (most recent call last): File "", line 1, in File "_sage_input_155.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("QSArIEI="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpsslTY3/___code___.py", line 2, in exec compile(u'A + B' + '\n', '', 'single') File "", line 1, in File "element.pyx", line 1296, in sage.structure.element.RingElement.__add__ (sage/structure/element.c:10903) File "coerce.pyx", line 765, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6996) TypeError: unsupported operand parent(s) for '+': 'Full MatrixSpace of 3 by 4 dense matrices over Rational Field' and 'Full MatrixSpace of 4 by 2 dense matrices over Rational Field' }}} {{{id=76| B * A /// Traceback (most recent call last): File "", line 1, in File "_sage_input_156.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("QiAqIEE="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpeQHkqt/___code___.py", line 2, in exec compile(u'B * A' + '\n', '', 'single') File "", line 1, in File "element.pyx", line 2282, in sage.structure.element.Matrix.__mul__ (sage/structure/element.c:14931) File "coerce.pyx", line 765, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6996) TypeError: unsupported operand parent(s) for '*': 'Full MatrixSpace of 4 by 2 dense matrices over Rational Field' and 'Full MatrixSpace of 3 by 4 dense matrices over Rational Field' }}} {{{id=74| /// }}}

You can add a scalar to a square matrix:

{{{id=72| A = matrix(QQ, 3, [1..9]) show( (A, A + 2/3) ) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rrr} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}\right), \left(\begin{array}{rrr} \frac{5}{3} & 2 & 3 \\ 4 & \frac{17}{3} & 6 \\ 7 & 8 & \frac{29}{3} \end{array}\right)\right)
}}} {{{id=67| /// }}}

Solving Linear Systems

A linear system of equations can be encoded as a single matrix equation $Ax = v$, where the problem is to solve for $x$ given $A$ and $v$.   In Sage, $v$ can be either a vector or a matrix.  If there are infinitely many solutions for $x$, exactly one is returned. 

{{{id=15| set_random_seed(1) A = random_matrix(QQ, 5, num_bound=100, den_bound=100); show(A) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} \frac{59}{78} & \frac{13}{14} & -\frac{11}{49} & -\frac{47}{75} & -\frac{52}{15} \\ \frac{27}{56} & -\frac{40}{51} & \frac{10}{53} & -\frac{89}{12} & -\frac{3}{16} \\ \frac{82}{61} & -\frac{55}{7} & -\frac{74}{45} & -\frac{11}{46} & \frac{5}{52} \\ -\frac{43}{32} & \frac{79}{37} & -\frac{57}{29} & -\frac{48}{29} & \frac{43}{15} \\ \frac{67}{47} & \frac{12}{23} & -\frac{25}{24} & \frac{13}{16} & \frac{46}{63} \end{array}\right)
}}} {{{id=14| show(A.det()) ///
\newcommand{\Bold}[1]{\mathbf{#1}}-\frac{33309120911318572378640943486889}{31089394772345027072747520000}
}}} {{{id=13| v = random_matrix(QQ, 5, 1, num_bound=100); show(v) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{r} -76 \\ 98 \\ -82 \\ 27 \\ 51 \end{array}\right)
}}} {{{id=21| x = A.solve_right(v); show(x) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{r} \frac{1423743250326764132356431158406816}{33309120911318572378640943486889} \\ \frac{403480176009266931788705978326932}{33309120911318572378640943486889} \\ \frac{1021661231928866958567656117461050}{33309120911318572378640943486889} \\ -\frac{393424222265393565078003995300100}{33309120911318572378640943486889} \\ \frac{1153927117568938940697661220942640}{33309120911318572378640943486889} \end{array}\right)
}}} {{{id=25| A*x == v /// True }}}

Or use the Matlab-style notation (backslash) for "solve right":

{{{id=26| show( A \ v ) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{r} \frac{1423743250326764132356431158406816}{33309120911318572378640943486889} \\ \frac{403480176009266931788705978326932}{33309120911318572378640943486889} \\ \frac{1021661231928866958567656117461050}{33309120911318572378640943486889} \\ -\frac{393424222265393565078003995300100}{33309120911318572378640943486889} \\ \frac{1153927117568938940697661220942640}{33309120911318572378640943486889} \end{array}\right)
}}} {{{id=22| v = random_matrix(QQ, 1, 5, num_bound=10^10); show(v) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} -4974445969 & 8392588976 & -6715020990 & 5267894129 & 2291762482 \end{array}\right)
}}} {{{id=12| x = A.solve_left(v); show(x) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} \frac{67321224149981102897044836468121794062400}{33309120911318572378640943486889} & -\frac{58191178220098475340223700966878389564576}{33309120911318572378640943486889} & \frac{6542978323837662469867345327738482339600}{33309120911318572378640943486889} & \frac{112312193705992854978737711658420821340640}{33309120911318572378640943486889} & -\frac{32574784206880022471192240591225325471024}{33309120911318572378640943486889} \end{array}\right)
}}} {{{id=30| show(x * A) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} -4974445969 & 8392588976 & -6715020990 & 5267894129 & 2291762482 \end{array}\right)
}}}

NOTE: You can also solve linear sytems symbolically by using the solve command, as illustrated below.  This is fine for small systems, but is massively less powerful for large systems.

{{{id=29| var('x1, x2, x3') S = solve([2*x1 + 3*x2 + 5*x3 == 1, -x1 + x2 + 15*x3 == 5, x1 + x2 + x3 == 1], [x1, x2, x3]) show(S) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left[\left[x_{1} = \left(\frac{18}{5}\right), x_{2} = \left(-\frac{17}{5}\right), x_{3} = \left(\frac{4}{5}\right)\right]\right]
}}}

Here is how to "get at" the solution:

{{{id=28| S[0][0] /// x1 == (18/5) }}} {{{id=32| S[0][0].lhs(), S[0][0].rhs() /// (x1, 18/5) }}}

Using matrices we could solve the same system as follows:

{{{id=37| A = matrix(QQ, 3, [2,3,5, -1,1,15, 1,1,1]) v = matrix(QQ, 3, 1, [1, 5, 1]) x = A \ v; show(x) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{r} \frac{18}{5} \\ -\frac{17}{5} \\ \frac{4}{5} \end{array}\right)
}}}

Solving over the rational numbers using Sage matrices is quite powerful.  For example:

{{{id=38| set_random_seed(1) A = random_matrix(QQ, 100, num_bound=10^10, den_bound=100) v = random_matrix(QQ, 100, 1, num_bound=10^10, den_bound=100) A[0] # just the first row /// (-9594630370/11, -2724596772/25, 1863701863/28, 9439355896/53, 3256466009/77, -2775999913/46, 6078482163/22, 5414436163/52, -8268812576/79, -4379454232/29, -2552665574/29, -470228069/4, -882326039/4, 3785590977/80, -1702862431/38, -3680531892/49, 3981058443/58, -6452386075/54, -9730288561/17, 4144563139/91, 2569655869/16, 5267894129/24, 2291762482/63, -121647930, -288367503/8, -5602596109, -944809119/13, -254970967/6, 9174595829/36, 9890125186/49, 1949069140/77, 4361694947/37, -3258855114/17, 7211366259/20, 4620352777/25, -4950769310/11, -798463088/9, -8071277437/54, -7428387699/25, -5802083483/69, -1032643213/11, 7890466475/96, 260728335/13, 3519763567/50, 5168574241/53, 6041585481/14, -8762788232/61, 9542318905/93, -6912304585/61, 7398500699/15, 9305117047/53, 5085798709/5, -892991609/7, -2215826603/71, 3597484937/92, 109187356/13, 3154488062/3, -871330581/26, 9049245821/10, -5234990449/83, -1665681937/69, 3354166217/69, -3545102319/17, -692086265/12, -399038357/3, -6334522202/31, -5440578711/23, -528417838/11, 249360565, 1173338630/9, 899149590, -9841152082/49, -3646052217/11, 2469709509/26, 5734318196/7, -110113084/87, -614233310/71, 355287176/7, -2502772821/4, -4250282843/16, -2324915517/20, 704030737/7, 1034336659/16, 612590839/12, -29057948/17, 298253077/50, -1830747314/41, -572760521/84, -7990601806/3, 1579513585/66, 252460987/6, 7930828803/70, -747589215/92, -704795663/41, 7019186788/75, -8420100094/61, 8962528344/67, 1364947304/13, -1949463324/13, 164457253/5) }}} {{{id=34| time x = A.solve_right(v) # Note: On my 64-bit OS X dual core i7 2.7GHZ laptop: # * in Sage-4.6.2, this takes: 0.45 seconds # * in Magma 2.17-4 this takes: 1.39 seconds # * in Mathematica 7.0 this takes: 10.5 seconds # * in Maple 14 this takes: 18.2 seconds /// Time: CPU 1.38 s, Wall: 1.38 s }}} {{{id=40| x[0] # this is just the first *entry* of the *massive* solution vector! /// (3180798594100769229330946513590216326962619994586668961428023904719644245358021076653746014528172494232696018883048852268592608059103415995040084384913381106739563027672394695493096871021781859157883607587418839500512178466404698302910088803505385026105438700902646670431769953067191852805080517504297344336120854892814446338928064478347415145078941541005891130660909402256773811534390001996684976491038206653171374676768554562876701475549297832800912685465572879821382612255710921945307117791086240779411728821482712753799960078481414609020421323192409436631807085286205733888330950349420646875388632419577107813727464661754228841863409955629118132665964933130073571683061939025405402917277657306737553519190404889079533211348733570380975715793137807260433660862352728188538884878558509435047575375181440162175548744014835812466321817078291266545032990984254074116453457843681812539597939612723509058702467434626298788126015571270941724940552428649700595808115612675086990532129548334545327831943242127659006741005797354045532414032688446529230206572023438037403424047843655221357855739570878879788955627030709940048090689663212691371374846157832629252662653450593931824648149494438971468827246694600512162829788363374644978005906254102412241712402292109073965368318231866592131630347452651206538528675132706115897888250656588127917994157583337895722343346061732259032500523359349644784846729690136013065102933848652252177236632575757825461761384729730784758965686899061030318280448465528152147455509371281335045582481180568207733108230902091949534780007856654924806858098413029945154216978487116933660817390206093704512060352089242869786549973792620363639115035815039524069200809970005768751194137484109473755878340086591941027540086869145432517498068196196208405681779911395176173152800289072122622913043268140909665534780322575175819404892667636938003593675275419212263641242598847785159302633443694997586740358212461217500127203585545649952194350052112260510188589882276548585423754313066590133892962780754576063534464552175428311882777408816713077415204271080476770017485170377557583187947472211851279481738126629008451107930728909095082215240023969251542335118983521441746141728767711776602576304200034129252792598085440528994635599176377326330667810965734373753350412534295600016181750483758396860402019260685380581167469451174506070573263048250504053343010564777369644163851161629614573867209965403823739622770993400340944456788864884780758680842626829862485739494383589998149451689086265919649350652848239730386990212845253778608814621345920880267110043371379247337766233014408839750130538270168452333078479545671118552599210175722504604538622408367383982101246655077873566448779004829045330034628842322666151340642932441304083615453925092610476197350612991446047069985143407637042427757626317469152814474770112062769115147001765954605976829122685052819398888420050270223238465698593721590569420428680666853651345442182497563804308295772202367544039134566267317283858360833842169427204779915005813122935013775343683002680114673227156000772804461723058149444658452987998408797054641448214177683512165439690960561803274185498689162066454330481608302840246433976181322060723359361172621150402317758912789894460069191728574009988158298422403220369112946430464887755068937913782105782789151249967366604386132004911016623691391716355816273952953832573552782916504577980667125309797591945442068758446030346292215620099461699578473012485972439783296395018536766628003410915357727707347414816706647862039889550733717519211310709677848762825556517150332798945963436118026684955469873460488723367082061136865283644406216437759891999789319903801079186806093392194164299767664737208300161428679133791690406184003545121086243197116322733537677712313360015010089193736228922064660310587615979247354911579430777842752936679480669052529411070119656341258770037500975400385195298743206183325681964302065261773521332336898733489131741722082285273/978260603094798303931500784313168718254902382181231467798181881474642450807982964932313479693371353192807831701642483359976589112442878917506002848094579074551343217384535307513511590526687947973054198804152242828607540953784391166148577859865954566227698460072549558308448465323751151049984429438335388896498538105241973492859516508236099409741515193355117801130690742322640675132432221195363276016669584801701075030821133351683454217444473827237860010083779011557493974854801923675530498602116868812856327716865798847778176408267324754752835748788791607312992008239629821706749020761751177701522618368260803979688956448034639725335863929503905759249853041272314750161481723175876081628928949636523878518637442651453413819798835237452632082566335234362456917842279657616381476690500190062778295953055031631007859456658211505771782742688891209543218790450968453535010433768503760718454199495724849988205819767428163060745427354888415357665999263534637928364412915788691915761966335973373055457007173529940937475442382273452669524187332570395388177133535140201789485616287251263531025940576426543409491106967659883548461893102624594873475421971187192508245276725780121920410931253159024456201726999431094314842928133135803326564251039500134424844450091708976217056029080368561416754776998242525545481873761515884372968708864088080377816361498838605048531484868733885639253565194333546053519693688165599485092202586646396190487842749718131479320095845510367625728693998379325051194774889800031237126406984245840644743555680373549384742517894195690246447314741956700303487107231430613552298104782839986407568522697778249360358247829993692414038056649890435269184170223940500817621284605818084573347436004697583464755586015288857852938036684384899736370074553406016052694167803350874045296454506695143007307468258648858499458216888618781584907537940422067486613735982306191718452768614639493548374222450426130748543309327877903243013212369534028466568861722687685543113015390698866846227175463563489609929623995920742023995961843384505226810852159739811291172995331159132989953496725094872825027259146696572719256568712559552613305763497555197231675732185457144732356256987521869711914109835892364311884655177207418916316055528951207523824411888642734963323937416184028281137921475636110624393948172574186279261805589162654764845733978778360394870680634931489839358649433751180013933508213529164876743323937612531365880370425559092382210631870040537648908064333879535441145267455984854015002471190661985996867552518396777371913435039665424599088721935977990599110447251665776993675975660434799814104485034871855519698237146427729835125644584488984451154371635620957081584575624924873811833854279625480187538016512794669217277197392118218722394352723531566560087322956553044033452473143289357634876678985598219700188168537437617083244401789131961177248111829550993737298850685838685126102983967384271963936609361201709229231088910532209368094287539997994966232275786393704250012807544733473395886846693933373527847189530412766425827228098494620858389984618382946050331650879526406250111882043566832959572363058806438918844389356077671046589513669924144767220218520837070854790560593024255847528138659021319270537818277079672365946794480087848617423315994155973450063121222467147510265656560298760737042057562110577647804194329315752976058827975359818508594558744105769005597126406238664504520086971829746917549424323752955060091632271146368020008609621051514672116600419418800522730400147227469405861558692778319159476408222824499057155400584022374629850660343118191900251694140640745153860703874828592186213693369241078033007873363982752540841706199878349627856145520531915773262634154896604865836447398507271244839714243759487744619686820807465574970137891761049649700001823980273667542639680639294330031129946950526458427179065591166386965096212834802688773598798739138541512914682889802208027983942786313225857136045234736171807948234712) }}} {{{id=33| len(x.str()) /// 789999 }}} {{{id=57| /// }}}

Characteristic Polynomial 

The characteristic polynomial (charpoly) of a square matrix $A$ is $f(x) = \det(A-x)$; it has the property that $f(A) = 0$.

{{{id=59| A = matrix(QQ, 5, [1..25]); show(A) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{array}\right)
}}} {{{id=56| f = A.characteristic_polynomial() print f print f.factor() /// x^5 - 65*x^4 - 250*x^3 x^3 * (x^2 - 65*x - 250) }}} {{{id=60| f(A) /// [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] }}} {{{id=61| R. = QQ[] (x - A).det() /// x^5 - 65*x^4 - 250*x^3 }}}

Internally, Sage using some very clever algorithm in the Linbox C++ library to compute the characteristic polynomial, so Sage is fairly fast at this.

{{{id=62| set_random_seed(0) A = random_matrix(QQ, 200) time f = A.charpoly() # NOTE: # On my laptop, Magma and Sage both take 0.7 seconds to compute this characteristic polynomial. # Mathematica takes 338 seconds (=nearly 6 minutes) /// Time: CPU 2.48 s, Wall: 2.48 s }}}

For this 200x200 matrix, the answer is already huge:

{{{id=63| f /// WARNING: Output truncated! full_output.txt x^200 - 9*x^199 - 181/4*x^198 + 49283/8*x^197 - 457779/16*x^196 - 304737/4*x^195 + 22838493/2*x^194 - 1420220793/16*x^193 - 398168119443/256*x^192 + 13761192752881/256*x^191 - 68087215326165/512*x^190 - 7203771666207709/512*x^189 + 736387403204317605/4096*x^188 + 9806918565374371073/8192*x^187 - 199513046609368783991/8192*x^186 + 732723662119534986273/16384*x^185 + 16836339811203477712895/4096*x^184 - 9696364055839238220136487/131072*x^183 + 361040892565722092859224129/262144*x^182 + 1632020105945166214624258103/262144*x^181 - 149046750176193102141994928941/1048576*x^180 + 601793607446729213076630649507/524288*x^179 + 195197061623351112093062061939979/4194304*x^178 + 1011948649059061312104264414331691/4194304*x^177 - 45891432160515868084463612099017799/8388608*x^176 + 7795526118101487074068368153517921433/33554432*x^175 - 56127973055756658243207426902511936483/33554432*x^174 - 1506412569021046563602414433620046269515/67108864*x^173 + 83318439291066578293875031415639018065009/134217728*x^172 - 4526974607841104449601536169579388245363917/536870912*x^171 + 26263556060505502887385720500020874156234333/1073741824*x^170 - 2760228882195697571160127345742641111688339239/2147483648*x^169 + 84814862159821230756405094838621956112477422227/4294967296*x^168 - 1732497969802874015562115694066401468913119057725/8589934592*x^167 + 10524336812993457379234493137575097533424033158521/2147483648*x^166 + 194698953568273407507923692016039711640553773800855/17179869184*x^165 + 3053797831962821205828320507897787649437808573008657/34359738368*x^164 + 746448993774935375514789689702133280856116850489803927/68719476736*x^163 + 11883690526592573293842050536734797548678103959867711045/274877906944*x^162 + 2350683300923478092249612202232677414836486464437496568971/549755813888*x^161 - 6002375700023223605959264814817233895345701213494906265387/549755813888*x^160 + 616651623209640266459758939016160761056649489768496154324719/2199023255552*x^159 - 8740278479813555308917681247661283829485752578144452230196535/2199023255552*x^158 + 387602390186014347265160035893612383081312590373131930232829991/4398046511104*x^157 + 683575397940580704734064947229774898925997373279978135786667651/17592186044416*x^156 - 466313787268129825745913991652753913690398091300443994159455532045/35184372088832*x^155 + 42180559946051162590831009256885262578248991264730006773624719406281/70368744177664*x^154 - 328676256853308241176888902326913935475797393078508473916683764391977/35184372088832*x^153 + 250359961511436025027005390982247717814280359395094238139353843776933/35184372088832*x^152 + 177969052904501207938033502486807200133367701936277453992577826396788129/281474976710656*x^151 + 4702782184174826257429867219108248340165258021016360632930754239273555523/562949953421312*x^150 + 17965559681619728151276457892963009795511193877102501479243973391484302227/1125899906842624*x^149 - 446347458763876253071378525520968092107922092395780055716716654927117408809/4503599627370496*x^148 + 49981289272272044708034039851218397670555568219480075730781535187567597424775/4503599627370496*x^147 + 6135764130108074875798180434242614468833748945814379108874809178222394529606979/18014398509481984*x^146 + 12539717962857480094414739043636922958510837026627566344491878529967077597567235/2251799813685248*x^145 - 746687582449298724560875204282840442408673623056241552914723333136629607404757567/18014398509481984*x^144 - 26191176165637045506519529723882487257549668638216147164921598915455327055256669793/144115188075855872*x^143 - 203196001334763891609383974414442496069755507322992072655475808992900691150074457341/288230376151711744*x^142 - 6405161259701785542538132501241174047072070782857646247697387320728984241415457232379/288230376151711744*x^141 - 79247853104316718285229647431466315762450014450788648366500845470912456029256844188727/576460752303423488*x^140 - 47865669986060908804609895517535404499098835911874656644307361992538967534699476396832301/2305843009213693952*x^139 - 545182383855311995122686918216357306001414029938763349514453586856803687308971010024053343/1152921504606846976*x^138 + 80886687518242610679652007154046061552698079387831758648132071799758112345624954394510846163/9223372036854775808*x^137 - 234593981078206025776908687945185829543194203029138964119729202647565121421240097857576553075/9223372036854775808*x^136 - 2265088142817410357044059406350468402875119263962781036813504873328078940165243679445878842727/9223372036854775808*x^135 - 1107589973498610198667062974156493487904521996729337660041941838986465767124011147674199008938635/73786976294838206464*x^134 + 12048347691322279128330339439949711442532648177035514277664183855717434539093811731566281280840495/73786976294838206464*x^133 + 78250272026912575542136308987275232574086710654042788403509281010803091722172384858395106503292687/295147905179352825856*x^132 + 889710238224291296414117689903568847863821833616913250220197982603275207896639912167004119685560121/590295810358705651712*x^131 - 358174773979617139645890745759943849970351772530890194856660252117123670707016921398715949594743548239/1180591620717411303424*x^130 - 9451151444619435899861250159588272909338600740100564538195695548550214919308281528325233929962201269387/2361183241434822606848*x^129 + 177193218986207953733774074379429029248386636096272791346706130472868486773831784639998497048172338498717/2361183241434822606848*x^128 - 13419813841507432502826806465967260923884058915575005070397988969185162873749964541176816149419080725461441/9444732965739290427392*x^127 + 21996879372225512134740868632314394737035585445388833700255687552615256098835602260161579815641005309024479/2361183241434822606848*x^126 - 1739275904654785766786754430788061161834313677576126462948356665532292963265617948520112472214532989555321705/9444732965739290427392*x^125 + 41739663994191859866430842861822226979043227166300498183244028237077430952385649679642491837313704785189763509/37778931862957161709568*x^124 - 459955946786739036635369293173306837268216141237431881909574334836213410719924550411452212349636597711933946473/75557863725914323419136*x^123 + 3284494630139122060667065789787187231907761680586128358026386382990710675287802929214189291570285019022003707723/302231454903657293676544*x^122 - 508433438222347619228546597699442888235133240971429793606334261594865710238509497044780098737607968293286326569279/604462909807314587353088*x^121 - 32346373453596516821365139064608262929356603006145849210785925399305282161796422659527752065598347253210080771056303/1208925819614629174706176*x^120 + 1234901603029406252315348315105885724957865040305311343054010756067472145340490329762311959957522098340784393138884029/2417851639229258349412352*x^119 - 24231741661297492267048890466341283228425696144855393816166925518169447051726413951875896611440388881154017507624177019/2417851639229258349412352*x^118 + 896494510379039402768166024469213750299453692467300871097269115448775407399029118281217862769164101094914356926896271003/9671406556917033397649408*x^117 - 1031677426667903368427714888790300239192391859668308383989644703549596629734115752566738267857689475958159993573963506193/1208925819614629174706176*x^116 - 233578641998323438887112285963372471584040797855935467018448945709002696485828700860385758331453138394696002876966722622675/38685626227668133590597632*x^115 + 1845024574791356983421885229386560938631667691201510388471008711164649346030974152610783359815512500474513002704342872786373/19342813113834066795298816*x^114 - 185572363959644997662771111386318913458565296807016155985501398932695711944690503843232771127844984733008307743823562557701457/154742504910672534362390528*x^113 + 1436682346118481602644683743998033466078908185121511615098193526030310556133761425650960718646160876753892693087082209621597343/154742504910672534362390528*x^112 - 122772925577519731207740233016507960992853612326031045888211403535466142404773595446949611266279423361240261106017585260781724229/618970019642690137449562112*x^111 + 3449718971963419796612106926581438928764172078229408066325924506264199757422919991974323074712009211034467840443123757585600627231/1237940039285380274899124224*x^110 - 10615267533787628272344686114583915566182740911880569941708330269782540579318839651476283056574815582940364538518314359444725540405/309485009821345068724781056*x^109 + 111401827373923784178286070149157572028330125139860855097594600516190349833753963218200025942241408732109324341570424465618353973377/309485009821345068724781056*x^108 - 7427240068777991910751966667447402818311343498787611744372481044311740138539370401564359121055946389985901522045498543898270952442773/4951760157141521099596496896*x^107 - 654628030699089528469955128284018311229984587303790734481600584988560739408519570149365278662600152326676123961854090567909044622282785/19807040628566084398385987584*x^106 + 1530015611176200857349888551626105161899539323430118474831514502706719338602820882677528564443805634759885273305387312437476043611656633/4951760157141521099596496896*x^105 - 322473291053116523301810779969932318248375974329501610623679368290666926961041721829127157431764459752088914885393725257963570809714604231/79228162514264337593543950336*x^104 + 4111061124285241354937982611437076838364467942133033351227987400392793752187729784620758736091350448413643591243709153865449527484775222519/79228162514264337593543950336*x^103 - 4907670249936516692587838457942546071990764001372408185072526638814308591733700018438750151643048687218589343999035157531407650784594318971/39614081257132168796771975168*x^102 - 2005964448213947164542814955440153467556391480981989821336819487395831032342541384593647880110912991330807237154833553286224056988092881918123/633825300114114700748351602688*x^101 + 3240429319496686191807876783034436975983125926533250989984599646464670300184972792151267896748246724752515357152122735538962561132010737043645/1267650600228229401496703205376*x^100 + 1781583346454855972162483631033208373778673635396694473806720227763865426672053533672398788276400720214662649947248131431311777446060455399695663/2535301200456458802993406410752*x^99 + 8609120139603002155779642619198392918895369168998602650572565528096474854651392655156355528152305774071141142615543321874193274751060303949345783/1267650600228229401496703205376*x^98 - 43084527492411763893872706424597657041340059676235465979938484650485721240368431625744960837070006608678491406581215946481891838633642314765059633/316912650057057350374175801344*x^97 + 19067212175841201003760063113117287543326971848579139298535759447526631759111422101157244857670541837971317579649687579247507401506178477997970804661/10141204801825835211973625643008*x^96 - 148589519474536655333786713197353202382988114650028908192146319533534831655937023718795726055901161175468585291694538836286317166759806853896121082109/20282409603651670423947251286016*x^95 + 1781258749485009431886288504501725989279853850312495107656397543778498840784387787054402576606908382563428462624975366133257001579938048431436082648285/40564819207303340847894502572032*x^94 + 14686262793796492985722125325863278139534387199367121001893482129907630908923257040877906876428783816059693314040429207708487655268708315043654870376023/20282409603651670423947251286016*x^93 + 4836777293601924100253585283197285983924506618021602532216866433441523453125386564409861121883161784673631956159648860554854016851462044678651505626223323/324518553658426726783156020576256*x^92 - 54160651790131455259911690625051814691965486176039528466056709442938416944148096759776993615215857430192361202981006905966129443541796132273798967877813723/649037107316853453566312041152512*x^91 - 84279052436197454671938918169425715500859826412433471816398742147626473528897933098177592819033779627500518615658488894417739728550207483497359794217577491/81129638414606681695789005144064*x^90 - 2952746995134326329625119391453825951400195556266996626592206230996811511673375093131776157854901253019093658591900446616532033175347238768494593113608047629/1298074214633706907132624082305024*x^89 + 1608869851119543624144065830457819619013658960387805896078187595252381536779425021167568697263013854329191771007849148848276053693738018064175053555189248062879/5192296858534827628530496329220096*x^88 + 969561667192365673585949787937298285092911261790867932801812276450749730451205796110214703530144042055742914636087954969540929454957748318947283844189528709963/10384593717069655257060992658440192*x^87 - 265507144207194325558694203058512259858605616666087873645877296219818987344577813876187791652307446577561861661928399765640008198199917241585809782049996749405615/20769187434139310514121985316880384*x^86 - 12276120718357446730621183334249484738088540206933191881399472697168665209830475166730814596671798310730688765915316761731507558667554345973683821720791087489350427/41538374868278621028243970633760768*x^85 + 328646366656879226098130386712361622904740713478021889184504619690543619495601901955188652761752959988582111643967094076260910079779080639255633374322543900935424359/83076749736557242056487941267521536*x^84 - 2422366122968501003153317870633503559080711785676782572696153425429132631885541703001098679954557833786101714350891207183766267732492804936805784779873364322053569437/166153499473114484112975882535043072*x^83 + 4008506809986275519488622388383220341615030388945070668194930353858468884331548152861117917265127050420331225724552188959392151680824293608615188424029852358989934555/332306998946228968225951765070086144*x^82 + 196287590733470311616001518223609634925568428843262512505005435129992442600142524924956527848433656734726001522073942107956484288684222494594155807186549815318705037983/332306998946228968225951765070086144*x^81 - 815669342190199070443278894006346339839267916807283733099830433157815340640957093857395295693811827657613750179655848749905883665986240306071440923320995021721331039953/664613997892457936451903530140172288*x^80 - 117362501411750744978375415154898916789608859829776481347407620040553357710572254471671480948752309458202580186687515454002831176090981703663829882807510978148798934146603/1329227995784915872903807060280344576*x^79 - 7696643243104751029480138295514870733722005145143860756828560112960695105913340999164375485359786650722513834206651488486272931462957977679306557351226169394696886090984549/5316911983139663491615228241121378304*x^78 + 966792641850436145118942450740454714033415304534111121525030340114455138207191372885870449142495792672964606799274132329038193856784771230342310110384300301604356506044223/332306998946228968225951765070086144*x^77 + 3164328012952922952827572691337400929355714256997235002308226499004693623246435465534271519036221447576651080024916959622111093949141799673537528423972494417135187594633800781/21267647932558653966460912964485513216*x^76 + 34960926714500383629655501719072927474594608140472293649239524299954844058757459281617255352435180736818412687195227107131820080150329818929658324003540596548015605849004264029/42535295865117307932921825928971026432*x^75 - 579580775011827551132532526978505725666044517172734297842749493970963199729534510314640493245299992319311628635450583960986170706798598349640934568773590828203852730502053742051/21267647932558653966460912964485513216*x^74 - 3302925708659322819144661914437002212620411338534530691358058505090131729001909790652153734938477798533946703444963286784698496498322247859668461246541894502438548673503276128389/170141183460469231731687303715884105728*x^73 + 43085230044424980948537427018215604337804644149721513733718623879023053076776512107046029983376059919310716896136640525652730260909455722494706991766869653659051841086281785576153/42535295865117307932921825928971026432*x^72 - 1594421393413128884347824392152457793010842259970146337117940681726791581171663649021644344432433450349113648461860670444507370800065882770584483086005185651212802992316810292622147/680564733841876926926749214863536422912*x^71 - 104877827488542401709212900566336222938318727826654496010584579692510885466108872911664996352412745608345929669610022627068221421000031265953726 ... 97340164206402622748204687009505806355695851403719165588288253437025949112383701627892490873448751369812128253857/11150372599265311570767859136324180752990208*x^54 + 317689064218082055463426563301751522384496557348419678014592363837515396516524746725160372209869775066787153937339895928705722808037941172398476715330400192096348970452769237407168020509241472522709890851/178405961588244985132285746181186892047843328*x^53 - 3528137571983191972541426325691893429655530232464359550242980176008955391684957396077722587956656711923457345130908049636919773340908903854376110494896803259454196454996776115776513352350887730502278368047/178405961588244985132285746181186892047843328*x^52 - 33415297802704369774683645244781504649057752195327262291718498257077528890461894249618832816033181373837490479257052085403072541503366390432478738782734913427099946790029587498091003266568589719624820758463/713623846352979940529142984724747568191373312*x^51 + 1218513974688297221556912760154143964272935262971296523167599020623522700986011627087439793131318593604737297291964186598974537737508717176970767849528490633689625280847398379004204179771895035468434782144163/713623846352979940529142984724747568191373312*x^50 - 7263862625068244745807729039125039353456669944889149000784238462951093086672666516326747396822677315568955711356390969166586207882492641018205307855654793393110076575583704981265156308845002774203519905358379/713623846352979940529142984724747568191373312*x^49 - 139465450059341461398034279118575486460717623667513811121545741147638422687718632290122231514168773627338277157780472801346235279309063481214787000267164688145266293996690301588099094267873646871742207910301595/5708990770823839524233143877797980545530986496*x^48 + 7973094099840289525753817426105930941383856819354699188637545841622968581509227608150415788951764770882070809956434390341735848979191198450130634982571483470183038418212443826754091238550741154486819112871975583/11417981541647679048466287755595961091061972992*x^47 - 37767270100214923612421707600337334240301909775614380529865670380415248995664535457849622459737335579908912189088567941188354083746271640295541110686696728512587197816055044235337355663413174598520060018641282979/11417981541647679048466287755595961091061972992*x^46 - 222090736773522007632182578538380596342038639556962328083923035752671934422922785570634493977454757945027855498465986351484438095102100950983889982773201581457542184620821498963198606151353630206290867777522223613/11417981541647679048466287755595961091061972992*x^45 + 1541153978232287810801165030490164228428963756423542162010815133570621294323523027970375043345509119103746940929527880388027199218809939290195382051408484669298408490218351548752349700270082717344160843484320525939/5708990770823839524233143877797980545530986496*x^44 - 117858926152380603862147459766931508129479495238752034072550702789577583294910147422961099675508424862093260987187927844084356473419892084109386149558615407694369887082802708183940542092240797227531588242392583754045/182687704666362864775460604089535377456991567872*x^43 - 915896966045442996509270732303326132747158184200700478401578352196481781904460985980086737537837730240496997664839838269559915222659837733237700141289730202081177747001707853474241212083819665351236519237808799237043/91343852333181432387730302044767688728495783936*x^42 + 36866882861689468462724950840564437708694949996462032304071956662440522754741638937558847838173045837024837273634349937858590151354458561906763423024993691003953338243382822411884323403535469901665314777868652423024823/365375409332725729550921208179070754913983135744*x^41 - 46887579829908332293467895203477168670369096256228373617915014795211587144301446269596618530386142471795908736541281118645932969746898787082370826937900094802105262075785128535934152581469519633734267134430085285405585/182687704666362864775460604089535377456991567872*x^40 - 6690264072193328393906236377275569288910854291607662792566326275584668990089988044274561427230823730865125735078289079348542870210889214561250241622512926269165946314339119587592529507949428365161501221231103802987524701/2923003274661805836407369665432566039311865085952*x^39 + 122850555434601517029842936336618008062863784093120097913598436801317362846662816536437057265921675741348465800547303550658005882711076927883701918209904027219303385436803164313435580504046033811905169287634290592587250227/5846006549323611672814739330865132078623730171904*x^38 - 281171159261792764868127917634530118872269903648121565302864416939144977689086101884881503131802160091333279470936364585811898936271823052203339381204851596637010921489950094064511898629252637232612931579925779336657819993/5846006549323611672814739330865132078623730171904*x^37 + 448273355094423303304917864106965237729974410023343081328323707068336510086499859228378492713880940842793211673145945310482973498456319212222609629937166562746722821853382021651109074510311791459588500650193190456228098467/5846006549323611672814739330865132078623730171904*x^36 - 2063485047488963073872853499724710319995744528744125419467671658032835695689403658555785886305030739040179357616542980077526695508687894651437003748274487212837287698622459170954978253853254780588367591888888857051374518785/23384026197294446691258957323460528314494920687616*x^35 + 105478207762991923185040196701653966486576831648435875840881531124703976840859557955408088699656889311157759644947113071384982760821328451516159663213270465707519397120325545943323194765899361049157224167801019918399962240391/46768052394588893382517914646921056628989841375232*x^34 + 9939729619609316439531846267789296937816418799687750219501315003101448021321056121033974777651271425286792945685182972765252730830282805600397512235441697422672498409931937884266202893559448052090658744699733119303421571447915/187072209578355573530071658587684226515959365500928*x^33 - 162675120223885947295053155826723147051342643007839439444514129918503309489731272411666292740256374055751529935201898054421119947519017971036030412714329518818743383250287537209384052564373848281261628837369414379355329969936789/374144419156711147060143317175368453031918731001856*x^32 - 404132891971450321432120947629503988705361786883500194919759586144103383418484774258886826281902792547640314262725462066957273173847949037942527773618455871373062983716483435444265544419537016012805493359005157416146863226423149/374144419156711147060143317175368453031918731001856*x^31 + 23771503664246664665495141359267250643801324264142102955525670046065667843228822242147071132463594470880087537879875640780966949146030391891700757294080948235614869548038296142899464263207399866243423903364463960226391959895452451/748288838313422294120286634350736906063837462003712*x^30 - 369181518771406705406996038601442219255785039464293838909479174182003623469571014788553374600334491483905293954453109356453056882572392596136790070872569394269063431727309386476188504888580357612660276528300571796553599158213976983/1496577676626844588240573268701473812127674924007424*x^29 - 131793779668268389970943918319466962535169413654198500251790484718014371462103659137522269950910788831151775849549777340348722277249296799227049403755063625825942245438857058384697202382291123547392303986113124038671234041991019501/748288838313422294120286634350736906063837462003712*x^28 + 88042217764502085742854654728700630601814764710672626475348210668606489050939032299035507898290902458082084010432794954351564123515513402395542658394928057095575249703724271993434105134671006499150699024587394394520014996922264566229/11972621413014756705924586149611790497021399392059392*x^27 - 690678855100099709380050312314429755793334628814991169042036484638451232782904406735419531943120617447343085363243920115518497142007597847098340141999045835388509934618041754974136076625768687567435593934448380543591225971885767219601/23945242826029513411849172299223580994042798784118784*x^26 - 256285361829098200590127900461264148465391738571969796905697437106519292569440173661804835906126964869510976729230675718219334229318613175091410043243700318370976884524697989712676056989721022073163890354735451384898673076465382940861/5986310706507378352962293074805895248510699696029696*x^25 + 125953521398493593958065085701649317257492086268911032207249897810114671098195302749306519872829970863094963848281620831895453641431416954067923143644180165083598560742800783958549551805213823074923605204374403067718381143117345824415253/95780971304118053647396689196894323976171195136475136*x^24 - 1115650705425678984882319027902882673517462920388055058000178119493109458856354820320813844672738710785772512100260558400993672339293786054140530160801831122723562467608796915918623400422782413369805951149715913823233160034211618484237709/191561942608236107294793378393788647952342390272950272*x^23 + 12920804269436963607836491729712030906729724211340399903423721320696164895632911784933242142538010061484663248737109185534920523870554291171028898684318731329408921354235736260684229407316567285076150783395960911869113446733043233462069465/383123885216472214589586756787577295904684780545900544*x^22 - 26509490032211403647095740676913484287522839429797135636358832252900916565859247028671359509834612818429828533496913347896960193122387900181025958809066935769133175439283867745375119307301205326180831020954387604476980707491514397828484661/383123885216472214589586756787577295904684780545900544*x^21 - 1314402998782991504179546199918639797198584723101703083481000426509479691461416188779551125328264243321214636268905766279476390749087183030879368813694196280412400164903161624627971433804405273218486804927026242346984725371120575846380368669/1532495540865888858358347027150309183618739122183602176*x^20 + 1594518909408095506883239482223889777081861335393620324580825018684792182766401098143214129289497283557738379673813401998845758181976062659306962530815014244210249171036582781029445215766350796729881434547759373483077667395453770242363918907/383123885216472214589586756787577295904684780545900544*x^19 - 8266434003667499046739303026384350979900794445768935164036372610386714658528869294117596621399293178883902532196438431658538711807511320344939287520696559883921994297477427676005681821313037696429902961497109584372246953716281758663312432415/6129982163463555433433388108601236734474956488734408704*x^18 - 748049732807938984203805616249158249784588163358300671338632560802510556436528924771032055170998583879828766747660136558629543479716298041589119006860720640454632479175347340994647731710330641119536484323874567633201657397341943300111014264675/12259964326927110866866776217202473468949912977468817408*x^17 + 2894653345302505223667142743805604041403665754779817766453155423247961680301055977901807114768386485894197073820552274578145850997539053776452310516403761479101500951709221568532056234559630284557885764846941000631293150270712232625206270609533/6129982163463555433433388108601236734474956488734408704*x^16 - 86384022480833940606579899055615443309475907104884395529556625481447608188911114418258891083927421164692418424129961287322464425807929662543936028786982178667016596888019776634758954790937018106322589717428291349003336640482701664045652750167179/49039857307708443467467104868809893875799651909875269632*x^15 - 326623331408356292457082206322108953671392368371610076259611788527857416183453848042402752302683991262793440112935629456113201822972218168428871513583039603699558432639474855951534628631527793650007574200428568210722092525866835935448288910724741/98079714615416886934934209737619787751599303819750539264*x^14 + 437083441931008430085993857474124274047296435880702062897962478355801679249814258806288910377532307469226040312453112511311347130742383636801299844696718014725279333831930356266168029265692117267732980383493258555366340324106677745415679001144651/49039857307708443467467104868809893875799651909875269632*x^13 - 1015392616970058450438381358410383582296523061445123263731316264105273878889715979484518834272284534695568009062738358906619144548310797581672089625337373412219870206931273571631052487475039758135070464254625415798577980991298882716128571854322629/24519928653854221733733552434404946937899825954937634816*x^12 + 115985857544057969889578137015582504164431000866885874165780873752272329135734465289947958136168682032181248523111260237853399232395538613889535447599102167386516941046321499307664157927434029977392114394280996447635305147959310697061376876095107313/784637716923335095479473677900958302012794430558004314112*x^11 + 628294621405071919567743380182295050174391382181934784656026683658085794023809841744759498424636552022188291697574710024700001252780473171385898113147250748958791862634543350644347193599892541120637074656689661265884578990508602440780075674401828639/392318858461667547739736838950479151006397215279002157056*x^10 + 8654032215719567885865395892413164135383623136952203002007054010143520258011864733223227237048863506151555509578152098397401824447420220338210579614933175602313900416274157946409175586604296246300866608974324522424628179152327220468404712447756219201/3138550867693340381917894711603833208051177722232017256448*x^9 - 2230192771287834575683749464991348066198599378703213038651419303812303645091543653951472332380818123037007163950596216796327915552238292225689993648656222995899299130734620689349568402599079538629227553771702905520218734279429029933715211910237691241/784637716923335095479473677900958302012794430558004314112*x^8 + 21177805088917147101413952936773834872097874747335437247327771923647096539920064751090853147170923976918317159888141910676955115487686490958132044077243199298078014067254574658597682267597500892023427060421125180738735146291270342261387064950120727763/12554203470773361527671578846415332832204710888928069025792*x^7 - 5682057406458564934978874409336431049675401645868957030517085942195881887509859114326822417178991132953297239477889334601733898036573739058397275986573194585335698039837612204273289142412923335364768269537099508027702445397034375847216730272230097861/3138550867693340381917894711603833208051177722232017256448*x^6 + 3304066702234509856469599089702298684410433261970168307700693563783593251864350184478031764118649867842890247256422818186376788268557547403760107609374245532373449101074176550176377515654966388571064835336850484996247030601525146938319551682903325473665/50216813883093446110686315385661331328818843555712276103168*x^5 - 14744445515292411439912962780317553132789486934691961663591467056571684194677000766398817216582506387304288245600773000984151603215986174811557367722916492224705433641386502083352351049258996279059211723589153410115896021014267394106765102454609165018731/100433627766186892221372630771322662657637687111424552206336*x^4 + 152703813897913024212616078083858134276102471840234155328371822801851681102145727497294041670359583005232573413816465724062793689310110337675071354810153763857938418912798141405686638329706277873047701746282796092627956661873101117972649822621304721433/25108406941546723055343157692830665664409421777856138051584*x^3 - 40660315255046666773630947011029229369914273919495940933783849844500986266204673575573245576160405764880199777031413836007390008788827338602028182590714287328590084073533915971115753088752090775732522391732183566499192248385969336384772554012735799236083/50216813883093446110686315385661331328818843555712276103168*x^2 + 2864038349147727210363413600812994468190056242033814230651163692470417814558529099554745208287526734196071187825160760310757216183424172186069487611303429282825820300109090493586609100940113578756154108530940316609183412567991029293931635598956275739530261/401734511064747568885490523085290650630550748445698208825344*x - 7152010842643586860947550113244403729920167076665719613820596708756275873239979813826389895574976128806703662327953118915301532732522996950153600690350114839985199391004038922429968866325289848822753633286348826555778518165373891045130805503068091142622915/1606938044258990275541962092341162602522202993782792835301376 }}} {{{id=66| /// }}} {{{id=55| /// }}}

Kernel (=Nullspace) and Image

{{{id=43| A = matrix(QQ, 3, 4, [1..12]); show(A) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{array}\right)
}}}

The right kernel of $A$ is the vector space of vectors $v$ such that $Av = 0$.  (The left kernel is those vectors with $vA = 0$.)

{{{id=45| V = A.right_kernel(); V /// Vector space of degree 4 and dimension 2 over Rational Field Basis matrix: [ 1 0 -3 2] [ 0 1 -2 1] }}} {{{id=47| V.basis() # vectors always get written as row vectors /// [ (1, 0, -3, 2), (0, 1, -2, 1) ] }}} {{{id=42| for v in V.basis(): print A * v /// (0, 0, 0) (0, 0, 0) }}} {{{id=49| A.echelon_form() /// [ 1 0 -1 -2] [ 0 1 2 3] [ 0 0 0 0] }}}

The column space (or image) of $A$ (acting from the right) is the vector space of linear combinations of the colums of $A$:

{{{id=48| V = A.column_space(); V /// Vector space of degree 3 and dimension 2 over Rational Field Basis matrix: [ 1 0 -1] [ 0 1 2] }}} {{{id=41| V.basis() /// [ (1, 0, -1), (0, 1, 2) ] }}} {{{id=53| /// }}} {{{id=52| /// }}} {{{id=3| /// }}}

Vector Spaces

When we computed the kernel of (the linear transformation defined by) a matrix above, the result is a "Vector space", which is a certain type of (usually infinite) set of vectors. 

The vector space $\QQ^3$ is the set of all 3-tuples of rational numbers.

{{{id=19| V = QQ^3; V /// Vector space of dimension 3 over Rational Field }}}

Let's construct two of the coordinate planes as subspaces.

{{{id=18| Wxy = V.span([ (1,0,0), (0,1,0) ]); Wxy /// Vector space of degree 3 and dimension 2 over Rational Field Basis matrix: [1 0 0] [0 1 0] }}} {{{id=17| Wyz = V.span([ (0,1,0), (0,0,1) ]); Wyz /// Vector space of degree 3 and dimension 2 over Rational Field Basis matrix: [0 1 0] [0 0 1] }}}

We can compute in Sage the intersection of these two subspaces, which is geometrically the $y$ axis:

{{{id=81| Wxy.intersection(Wyz) /// Vector space of degree 3 and dimension 1 over Rational Field Basis matrix: [0 1 0] }}}

We can also compute the sum, which is the set of all sums $v+w$, where $v \in W_{xy}$ and $w\in W_{yz}$.

{{{id=16| Wxy + Wyz /// Vector space of degree 3 and dimension 3 over Rational Field Basis matrix: [1 0 0] [0 1 0] [0 0 1] }}}

If we want to consider a subspace $W$ spanned by a particular list of vectors with that basis, use the span_of_basis command.

{{{id=85| W = V.span_of_basis([ (1,2,3), (4,5,6) ]); W /// Vector space of degree 3 and dimension 2 over Rational Field User basis matrix: [1 2 3] [4 5 6] }}} {{{id=88| W.basis() /// [ (1, 2, 3), (4, 5, 6) ] }}}

Given a vector we can ask if it is in $W$ or not, and if so, ask for its coordinates in terms of our basis for $W$.

{{{id=1| x = V([1,8,5]) x in W /// False }}} {{{id=89| x = V([7,8,9]) x in W /// True }}} {{{id=90| W.coordinates(x) /// [-1, 2] }}} {{{id=91| W.coordinate_vector(x) # sometimes getting a vector back is more useful /// (-1, 2) }}}

We can also define linear transformations (lienar maps) between vector spaces, e.g., by specifying where each basis vector goes.

{{{id=92| phi = Hom(W, V)([3*V.1 - V.2, V.2 - 3*V.1]); phi /// Free module morphism defined by the matrix [ 0 3 -1] [ 0 -3 1] Domain: Vector space of degree 3 and dimension 2 over Rational Field User ... Codomain: Vector space of dimension 3 over Rational Field }}} {{{id=94| W.0 /// (1, 2, 3) }}} {{{id=95| phi(W.0) /// (0, 3, -1) }}} {{{id=96| phi(W.1) /// (0, -3, 1) }}} {{{id=97| phi(W.0 + W.1) /// (0, 0, 0) }}} {{{id=98| phi.kernel() /// Vector space of degree 3 and dimension 1 over Rational Field Basis matrix: [ 1 7/5 9/5] }}} {{{id=99| phi.image() /// Vector space of degree 3 and dimension 1 over Rational Field Basis matrix: [ 0 1 -1/3] }}} {{{id=100| /// }}}