Vavilov_N_Konkretnaya_teoria_kolets

102 nikolaj wawilow

zADA^A (UMNOVENIE NA PROBNYE MATRICY). pROWERXTE, ^TO x ¢ test = d ¢ test, GDE

d = diag(x11 + : : : + x1n; : : : ; xn1 + : : : + xnn): aNALOGI^NO, test ¢ x = test ¢ d, GDE

d= diag(x11 + : : : + xn1; : : : ; x1n + : : : + xnn):

x 12. pROIZWEDENIE STOLBCA NA STROKU: TENZORNYJ RANG

1.mATRICY RANGA 1. pRIMENIM FORMULU PROIZWEDENIQ MATRIC K ^ASTNOMU SLU^A@ PROIZWEDENIQ STOLBCA NA STROKU.

tAKAQ MATRICA NAZYWAETSQ71 MATRICEJ RANGA 1. uPOMQNEM NESKOLXKO O^ENX POLEZNYH ^ASTNYH SLU^AEW \TOJ FORMULY:

²tEM SAMYM, KAVDAQ STANDARTNAQ MATRI^NAQ EDINICA QWLQETSQ MATRICEJ RANGA 1: eij = eifj.

²bOLEE OB]O, ESLI u 2 Rm | PROIZWOLXNYJ STOLBEC WYSOTY m, TO ufj | \TO MATRICA, U KOTOROJ j-J STOLBEC RAWEN u, A WSE OSTALXNYE \LEMENTY RAWNY

²aNALOGI^NO, ESLI v 2 nR | PROIZWOLXNAQ STROKA DLINY n, TO ei ESTX MATRICA, U KOTOROJ i-Q STROKA RAWNA v, A WSE OSTALXNYE \LEMENTY RAWNY 0.

2.uMNOVENIE MATRIC W TERMINAH MATRIC RANGA 1. eSLI x 2 M(l; m; R), y 2 M(m; n; R), TO ZAPISYWAQ xy W WIDE

xy = xey = x(e11 + : : : + emm)y = xe11y + : : : + xemmy = xe1f1y + : : : + xemfmy;

MY POLU^AEM E]E ODNO O^ENX POLEZNOE WYRAVENIE DLQ PROIZWEDENIQ DWUH MATRIC:

xy = x¤1y1¤ + : : : + x¤mym¤

w ^ASTNOSTI, OTS@DA SLEDUET, ^TO L@BAQ MATRICA WIDA xy QWLQETSQ SUMMOJ NE BOLEE, ^EM m MATRIC RANGA 1.

3. tENZORNYJ RANG. bUDEM GOWORITX, ^TO TENZORNYJ RANG MATRICY x

RAWEN r, I PISATX rk(x) = m, ESLI MATRICU x MOVNO PREDSTAWITX W WIDE SUMMY r MATRIC RANGA 1 I NELXZQ PREDSTAWITX W WIDE SUMMY MENX[EGO KOLI^ESTWA TAKIH MATRIC.

kOMMENTARIJ. iMEETSQ NESKOLXKO KONKURIRU@]IH OPREDELENIJ RANGA, STRO^NYJ RANG, STOLBCOWYJ RANG, RANG PO MINORAM I T.D., I MY WERNEMSQ K \TIM PONQTIQM W GLAWE ?. w BOLX- [INSTWE \LEMENTARNYH KNIG RANGOM PO UMOL^ANI@ NAZYWAETSQ SAMOE BESPOLEZNOE IZ WSEH OPREDELENIJ RANGA | RANG PO MINORAM. w BOLEE PRODWINUTYH U^EBNIKAH RASSMATRIWAETSQ

71pO ANALOGII S TENZORAMI, POLIWEKTORAMI I T.D. TAKU@ MATRICU BYLO BY ESTESTWENNO NAZYWATX RAZLOVIMOJ, ESLI BY TERMIN RAZLOVIMAQ MATRICA NE ISPOLXZOWALSQ W SOWER[ENNO DRUGOM SMYSLE, SM., NAPRIMER, mARKUS|mINK, STR.165.

w SPRAWEDLIWOSTI \TOJ FORMULY PRO]E WSEGO UBEDITXSQ PROIZWEDQ WY^ISLENIQ NEPOSREDSTWENNO PO OPREDELENI@ \LEMENTARNYH TRANSWEKCIJ W TERMINAH STANDARTNYH MATRI^NYH EDINIC. a IMENNO, PO OPREDELENI@

[tij(»); thk(³)] = (e + »eij)(e + ³ehk)(e ¡ »eij)(e ¡ ³ehk)

3. |LEMENTARNAQ GRUPPA. gRUPPA E(n; R), POROVDENNAQ WSEMI \LEMENTAR-

NYMI TRANSWEKCIQMI NAZYWAETSQ \LEMENTARNOJ GRUPPOJ

E(n; R) = htij(») j » 2 R; 1 · i =6 j ·i:

4. |LEMENTARNYE PSEWDOOTRAVENIQ. mATRICY WIDA di(") = e + (" ¡ 1)eii, GDE " 2 R¤, NAZYWA@TSQ \LEMENTARNYMI PSEWDOOTRAVENIQMI.

di(") = diag(1; : : : ; 1; "; 1 : : : ; 1);

GDE " STOIT NA i-M MESTE.

gRUPPA GE(n; R), POROVDENNAQ WSEMI \LEMENTARNYMI MATRICAMI.

x 15. |LEMENTARNYE PREOBRAZOWANIQ MATRIC

|LEMENTARNYM PREOBRAZOWANIEM MATRICY NAZYWAETSQ UMNOVENIE \TOJ MATRICY SPRAWA ILI SLEWA NA ODNU IZ PRIWEDENNYH W PREDYDU]EM PARAGRAFE \LEMENTARNYH MATRIC.

x 16. tOVDESTWA DLQ PROIZWEDENIQ

1. aSSOCIATIWNOSTX I DISTRIBUTIWNOSTX. uMNOVENIE MATRIC UDOWLE-

TWORQET DWUM WAVNEJ[IM TOVDESTWAM, ONO ASSOCIATIWNO I DISTRIBUTIWNO OTNOSITELXNO SLOVENIQ.

tEOREMA. uMNOVENIE MATRIC ASSOCIATIWNO W TOM SMYSLE, ^TO ESLI OPRE- DELENO ODNO IZ PROIZWEDENIJ (xy)z I x(yz), TO OPREDELENO I WTOROE I ONI RAWNY MEVDU SOBOJ: (xy)z = x(yz).

dOKAZATELXSTWO. ~TOBY BYLO OPREDELENO PERWOE PROIZWEDENIE, NEOBHODIMO, ^TOBY BYLO OPREDELENO PROIZWEDENIE xy, I PROIZWEDENIE (xy)z, DLQ \TOGO ^ISLO STOLBCOW x DOLVNO RAWNQTXSQ ^ISLU STROK y, A ^ISLO STOLBCOW xy (RAWNOE ^ISLU STOLBCOW y) DOLVNO RAWNQTXSQ ^ISLU STROK z. tEM SAMYM, DLQ NEKOTO-

RYH m; n; p; q IMEEM x 2 M(m; n; R), y 2 M(n; p; R), z 2 M(p; q; R). qSNO, ^TO PRI \TOM PROIZWEDENIE x(yz) TAKVE BUDET OPREDELENO I | TAK VE KAK I PROIZWEDENIE (xy)z | IMEET RAZMER m £ q. pO\TOMU PO OPREDELENI@ RAWENSTWA MATRIC NAM OSTALOSX LI[X UBEDITXSQ W TOM, ^TO MATRI^NYE \LEMENTY DWUH \TIH PROIZWEDENIJ NA SOOTWETSTWU@]IH MESTAH SOWPADA@T.

w SAMOM DELE, FIKSIRUEM KAKIE-TO INDEKSY 1 · i · m, 1 · j · q, I RASSMOTRIM \LEMENT ((xy)z)ij. nEPOSREDSTWENNOE WY^ISLENIE, ISPOLXZU]EE IZMENENIE PORQDKA SUMMIROWANIQ (KOTOROE MY PODROBNO OBSUVDALI W SWQZI S ASSOCIATIWNOSTX@ UMNOVENIQ MNOGO^LENOW!), POKAZYWAET, ^TO

^TO I TREBOWALOSX DOKAZATX.

nE PREDSTAWLQET TRUDA DOKAZATX I SLEDU@]EE UTWERVDENIE, USTANAWLIWA@- ]EE DISTRIBUTIWNOSTX UMNOVENIQ MATRIC OTNOSITELXNO SLOVENIQ, W SLU^AE, KOGDA SOOTWETSTWU@]IE SUMMY I PROIZWEDENIQ OPREDELENY.

pREDLOVENIE. pREDPOLOVIM, ^TO x; y 2 M(m; n; R), A z; w 2 M(n; p; R). tOGDA (x + y)z = xz + yz I x(z + w) = xz + xw.

dOKAZATELXSTWO. sTANDARTNOE WY^ISLENIE, ISPOLXZU@]EE SWOJSTWA OPERACIJ W R.

2. nEKOMMUTATIWNOSTX UMNOVENIQ MATRIC. sRAZU OTMETIM, ^TO UMNO-

VENIE MATRIC NEKOMMUTATIWNO (\TO ODNO IZ PERWYH NEKOMMUTATIWNYH UMNOVENIJ, POQWIW[IHSQ W MATEMATIKE, ONO BYLO OPREDELENO k\LI ^EREZ DWA GODA POSLE OTKRYTIQ KWATERNIONOW gAMILXTONOM). oNO NEKOMMUTATIWNO PO KRAJNEM MERE PO TREM SLEDU@]IM PRI^INAM:

²wO-PERWYH, ESLI PROIZWEDENIE MATRIC W ODNOM PORQDKE OPREDELENO, OTS@DA NE SLEDUET, ^TO I PROIZWEDENIE W OBRATNOM PORQDKE TOVE OPREDELENO. nAPRIMER, ESLI x 2 M(m; n; R), y 2 M(n; p; R), TO PROIZWEDENIE xy OPREDELENO, NO PROIZWEDENIE yx OPREDELENO TOLXKO W SLU^AE, KOGDA m = p.

²wO-WTORYH, DAVE ESLI OBA PROIZWEDENIQ OPREDELENY, ONI MOGUT IMETX RAZNYJ RAZMER: ESLI x 2 M(m; n; R), y 2 M(n; m; R), TO KAK xy, TAK I yx OPREDELENY, NO PRI \TOM xy 2 M(m; R), W TO WREMQ KAK yx 2 M(n; R). nAPRIMER, KAK MY UVE ZNAEM, PROIZWEDENIE STROKI DLINY n NA STOLBEC WYSOTY n ESTX SKALQR, NO PROIZWEDENIE TOGO VE STOLBCA NA TU VE STROKU ESTX KWADRATNAQ MATRICA PORQDKA n.

²w TRETXIH, DAVE ESLI OBA PROIZWEDENIE xy I yx OPREDELENY I IME@T ODINAKOWYJ PORQDOK, TO ONI SOWER[ENNO NE OBQZATELXNO RAWNY DAVE ESLI UMNOVENIE W SAMOM KOLXCE R KOMMUTATIWNO. w \TOM LEGKO UBEDITXSQ NA PROSTEJ[IH PRIMERAH, RASSMATRIWAQ MATRICY PORQDKA 2 NAD CELYMI ^ISLAMI. sKAVEM, ESLI

STANDARTNYE MATRI^NYE EDINICY, TO e11e12 = e12, W TO WREMQ KAK e12e11 = 0.

zAME^ANIE. pOSLEDNIJ PRIMER POKAZYWAET E]E ODNO NEOBY^NOE SWOJSTWO UMNOVENIQ MATRIC: PROIZWEDENIE DWUH NENULEWYH MATRIC MOVET BYTX NULEWYM. pO\TOMU, KOGDA MY WWEDEM W MNOVESTWE KWADRATNYH MATRIC M(n; R), n ¸ 2, STRUKTURU KOLXCA, \TO BUDET KOLXCO S DELITELQMI NULQ.

kOMMENTARIJ. nEKOMMUTATIWNOSTX UMNOVENIQ MATRIC DOLVNA U^ITYWATXSQ WO WSEH WY^ISLENIQH. nAPRIMER, ^ASTO PRI OPERACIQH S MATRICAMI NA^INA@- ]IE ISPOLXZU@T OBY^NYE FORMULY SOKRA]ENNOGO UMNOVENIQ, TIPA x2 ¡ y2 = (x ¡ y)(x + y). oDNAKO, KAK POKAZYWA@T PROSTEJ[IE PRIMERY, DELATX \TOGO NELXZQ! dOSTATO^NO WZQTX ZDESX x = e12, y = e21. |TO OTNOSITSQ KO WSEM OBY^NYM FORMULAM. sKAVEM, W MATEMATI^ESKOM ANALIZE IZWESTNA FORMULA (1=f)0 = f0=f2, NO DLQ MATRIC \TA FORMULA PRINIMAET DRUGOJ | GORAZDO BOLEE

ESTESTWENNYJ!!! | WID. a IMENNO, ESLI f = (fij), TO (f¡1)0 = f¡1f0f¡1, GDE g0 = (fij0 ).

x 17. wY^ISLITELXNAQ PERSPEKTIWA: ALGORITM {TRASSENA

1. aLGORITM {TRASSENA DLQ MATRIC STEPENI 2. rASSMOTRIM UMNOVENIE 2 £ 2 MATRIC NAD ASSOCIATIWNYM KOLXCOM R. dLQ DALXNEJ[EGO WESXMA SU]ESTWENNO, ^TO KOLXCO R NE PREDPOLAGAETSQ KOMMUTATIWNYM! pUSTX a; b 2 M(n; R) I c = ab:

GDE cij = ai1b1j + ai2b2j, ^TO TREBUET WOSEMX UMNOVENIJ. nA PERWYJ WZGLQD PREDSTAWLQETSQ, ^TO WSE \TI UMNOVENIQ NEOBHODIMY I, TEM SAMYM, ^ISLO 8 ZDESX NEWOZMOVNO UMENX[ITX. sEJ^AS PROIZOJDET NE^TO SOWER[ENNO FEERI^ESKOE72;73. `.i.mANIN ZAMETIL, ^TO SLEDU@]AQ LEMMA QWLQETSQ ODNIM IZ 10 SAMYH ZAME^ATELXNYH MATEMATI^ESKIH IZOBRETENIJ XX WEKA.

lEMMA {TRASSENA. pROIZWEDENIE DWUH 2 £ 2 MATRIC MOVNO WY^ISLITX PROIZWEDQ SEMX UMNOVENIJ I 18 SLOVENIJ W KOLXCE R.

dOKAZATELXSTWO. wY^ISLIM

d1 = (a12 ¡ a22)(b21 + b22); d2 = (a11 + a22)(b11 + b22); d3 = (a11 ¡ a21)(b11 + b12); d4 = (a11 + a12)b22; d5 = a11(b12 ¡ b22); d6 = a22(b21 ¡ b11); d7 = (a21 + a22)b11;

iZ \TOJ LEMMY LEGKO WYWESTI, ^TO UMNOVENIE DWUH MATRIC TREBUET NE BOLEE O(nlog2(7)) OPERACIJ.

tEOREMA {TRASSENA. ~TOBY WY^ISLITX PROIZWEDENIE DWUH 2n £2n MATRIC, DOSTATO^NO PROIZWESTI NE BOLEE 7n UMNOVENIJ W KOLXCE R.

dOKAZATELXSTWO. iNDUKCIQ PO n. dLQ n = 1 UTWERVDENIE UVE DOKAZANO@ pREDPOLOVIM, ^TO UVE IZWESTNO, ^TO UMNOVENIE DWUH 2n £ 2n MATRIC TREBUET 7n UMNOVENIJ, POKAVEM, ^TO TOGDA PEREMNOVENIE DWUH 2n+1 £ 2n+1 MATRIC TREBUET 7n+1 UMNOVENIJ. w SAMOM DELE,

WOSPOLXZUEMSQ IZOMORFIZMOM M(2n+1; R) » M(2; M(2n; R)) I RASSMOTRIM MATRICY STEPENI

=

2n+1 KAK BLO^NYE 2£2 MATRICY c BLOKAMI RAZMERA 2n £2n. tOGDA PO LEMME UMNOVENIE TAKIH MATRIC TREBUET 7 UMNOVENIJ BLOKOW 2n £ 2n, A PO INDUKCIONNOMU PREDPOLOVENI@ KAVDOE UMNOVENIE TAKIH BLOKOW MOVNO OSU]ESTWITX ZA 7n UMNOVENIJ W KOLXCE R. tAKIM OBRAZOM, WSEGO MY PROIZWELI 7 ¢ 7n = 7n+1 UMNOVENIE W R.

pO PORQDKU OCENKA {TRASSENA DAET n2;807. oKOLO 10 LET \TA OCENKA OSTAWALASX NEPREWZOJDENNOJ, NO POTOM BYLI POLU^ENY MNOGO^ISLENNYE ULU^[ENIQ.

72f.{TRASSEN, aLGORITM gAUSSA NE OPTIMALEN. | kIBERN. SB., NOW. SERIQ, WYP. 7. | mIR., m., 1970, S.67{70.

73sM., TAKVE a.aHO, dV.hOPKROFT, dV,uLXMAN, pOSTROENIE I ANALIZ WY^ISLITELXNYH ALGORITMOW. | mIR, m., 1979, S.1{536.

x 18. wY^ISLITELXNAQ PERSPEKTIWA: PORQDOK UMNOVENIJ

aSSOCIATIWNO LI UMNOVENIE MATRIC NAD ASSOCIATIWNYM KOLXCOM? sME[NOJ WOPROS | MY VE DOKAZALI, ^TO UMNOVENIE MATRIC ASSOCIATIWNO!! dA, NO MY DOKAZALI \TO S TO^KI ZRENIQ MATEMATIKA. sEJ^AS MY DOKAVEM, ^TO S TO^KI ZRENIQ WY^ISLITELQ UMNOVENIE (NEKWADRATNYH) MATRIC NASTOLXKO NEASSOCIATIWNO, NASKOLXKO \TO MOVNO SEBE PREDSTAWITX74;75;76.

pREDPOLOVIM, ^TO DLQ UMNOVENIQ MATRICY x 2 M(m; n; R) NA MATRICU y 2 M(n; p; R) TREBUETSQ mnp UMNOVENIJ. w DEJSTWITELXNOSTI, KAK MY ZNAEM, \TA OCENKA ZAWEDOMO QWLQETSQ ZAWY[ENNOJ, NO \TO NE WLIQET NA NA[ OKON^ATELXNYJ REZULXTAT. rASSMOTRIM PROIZWEDENIE TREH MATRIC xyz, GDE z 2 M(p; q; R), I OCENIM KOLI^ESTWO UMNOVENIJ, TREBUEMOE DLQ WY^ISLENIQ \TOGO PROIZWEDENIQ W ODNOM I W DRUGOM PORQDKE.

±wNA^ALE WY^ISLIM (xy)z. wY^ISLENIE PROIZWEDENIQ xy TREBUET mnp UMNOVENIJ W KOLXCE R I DAET MATRICU RAZMERA mp. tEPERX DLQ WY^ISLENIQ (xy)z NUVNO PRODELATX E]E mpq UMNOVENIJ. iTOGO, DLQ WY^ISLENIQ (xy)z NAM PONADOBILOSX mnp + mpq = mp(n + q) UMNOVENIJ.

±s DRUGOJ STORONY, WY^ISLENIE x(yz) NA^INAETSQ S WY^ISLENIQ yz, KOTOROE TREBUET npq UMNOVENIJ W KOLXCE R I DAET MATRICU RAZMERA nq. tEPERX DLQ WY^ISLENIQ x(yz) NUVNO PRODELATX E]E mnq UMNOVENIJ. tAKIM OBRAZOM, DLQ WY^ISLENIQ x(yz) NAM PONADOBILOSX npq + mnq = (m + p)nq UMNOVENIJ.

qSNO, ^TO, WOOB]E GOWORQ, mp(n + q) 6= (m + p)nq. lEGKO WIDETX, ^TO PRAWILXNAQ STRATEGIQ DLQ MINIMIZACII KOLI^ESTWA UMNOVENIJ SOSTOIT W TOM, ^TOBY NA KAVDOM [AGE POLU^ATX MATRICU SAMOGO MALENXKOGO WOZMOVNOGO RAZMERA. nAPRIMER, WY^ISLENIE PROIZWEDENIQ SLU^AJNYH MATRIC RAZMEROW x 2

M(1000; 1000; R), y 2 M(1000; 10; R), z 2 M(10; 1000; R) W PORQDKE x(yz) TREBU-

ET PO^TI W 50 RAZ BOLX[E UMNOVENIJ, ^EM WY^ISLENIE PROIZWEDENIQ (xy)z, A IMENNO 1:01 ¢ 109 PROTIW 2 ¢ 107. fAKTI^ESKI KOMPX@TERNYJ \KSPERIMENT POKAZYWAET, ^TO WY^ISLENIE PROIZWEDENIQ x(yz) ZANIMAET W SREDNEM PRIMERNO W 20 RAZ BOLX[E WREMENI, ^EM WY^ISLENIE PROIZWEDENIQ (xy)z, WIDIMO POTOMU, ^TO PRI WY^ISLENII PROIZWEDENIQ MATRIC PRODELYWA@TSQ NE TOLXKO UMNOVENIQ, NO I DRUGIE OPERACII. pONQTNO, ^TO DLQ MATRIC BOLX[EGO RAZMERA \TA RAZNICA STANOWITSQ E]E BOLEE ZAMETNOJ. dLQ NESKOLXKIH MATRIC, NEKOTORYE IZ RAZMEROW KOTORYH IME@T PORQDOK 106, A NEKOTORYE DRUGIE MALY, WY^ISLENIE PROIZWEDENIQ W ODNOM PORQDKE PROIZWODITSQ ZA SEKUNDY, A W DRUGOM TREBUET NESKOLXKIH SUTOK. tEM SAMYM, S WY^ISLITELXNOJ TO^KI ZRENIQ RASSTANOWKA SKOBOK W PROIZWEDENII MATRIC ISKL@^ITELXNO WAVNA!!!

nEASSOCIATIWNOSTX PROIZWEDENIQ S TO^KI ZRENIQ SLOVNOSTI WY^ISLENIJ HORO[O WIDNA UVE PRI IZU^ENII DEJSTWIQ KWADRATNYH MATRIC NA STOLBCAH. w SAMOM DELE, PUSTX h; g 2 M(n; R), A u 2 Rn. tOGDA WY^ISLENIE PROIZWEDENIQ gu TREBUET n2 UMNOVENIJ (W DANNOM SLU^AE OCENKA NEULU^[AEMA, PRI UMNOVENII STOLBCA NA MATRICU NAD KOMMUTATIWNYM KOLXCOM R NIKAK NE OBOJTISX MENX[IM KOLI^ESTWOM UMNOVENIJ W R!). tAKIM OBRAZOM, WY^ISLENIE h(gu) TREBUET 2n2 UMNOVENIJ. a WOT DLQ NAIWNOGO WY^ISLENIQ (hg)u NUVNO n3 + n2

74S.S.Godbole, On e±cient calculation of matrix chain products. | IEEE Trans. Comput., Ser. C, 1973, vol.22, N.9, p.864{966.

75Y.Muraoka, D.J.Kuck, On the time required for a sequence of matrix products. | Comm. Assoc. Comp. Mach., 1973, vol.16, N.1, p.22{26

76a.aHO, dV.hOPKROFT, dV.uLXMAN, ibid., S.83{85.

UMNOVENIJ. kAK MY ZNAEM, ^UTX BOLEE IZO]RENNYJ SPOSOB DEJSTWIQ POZWOLQET PONIZITX OCENKU n3, NO WEDX NE DO n2. |TO SOOBRAVENIE O^ENX POLEZNO, ESLI NAM NUVNO WY^ISLITX ODIN \LEMENT PROIZWEDENIQ m MATRIC PORQDKA n W SLU^AE, KOGDA ^ISLO m << n. mY TOLXKO ^TO UBEDILISX, ^TO DLQ \TOGO DOSTATO^NO O(n2) UMNOVENIJ, A WOWSE NE O(n3) I DAVE NE O(n2;701).

x 18. aLGEBRA KWADRATNYH MATRIC

rEZ@MIRUEM SWOJSTWA OPERACIJ NAD MATRICAMI, O KOTORYH [LA RE^X WY[E, W ^ASTNOM SLU^AE KWADRATNYH n £ n-MATRIC NAD ASSOCIATIWNYM KOLXCOM S 1.

1. kOLXCO KWADRATNYH MATRIC. oTMETIM, PREVDE WSEGO, ^TO DWE KWADRATNYH MATRICY ODINAKOWOGO RAZMERA WSEGDA MOVNO PEREMNOVITX.

M1 aSSOCIATIWNOSTX: 8x; y; z 2 M(n; R), (x + y) + z = x + (y + z); M2 sU]ESTWOWANIE EDINICY: 9e 2 M(n; R), 8x 2 M, ex = x = xe;

a IMENNO, EDINICEJ OTNOSITELXNO UMNOVENIQ, KAK RAZ I QWLQETSQ EDINI^NAQ MATRICA PORQDKA n. oB_EDINQQ \TI SWOJSTWA S AKSIOMAMI A1{A4, D1, D2, MY MOVEM REZ@MIROWATX.

tEOREMA. dLQ ASSOCIATIWNOGO KOLXCA R S 1 MNOVESTWO M(n; R) KWADRAT- NYH MATRIC QWLQETSQ ASSOCIATIWNYM KOLXCOM S 1 OTNOSITELXNO OPERACIJ SLOVENIQ I UMNOVENIQ MATRIC.

w TO VE WREMQ, KAK MY UVE ZAMETILI, PRI L@BOM n ¸ 2 \TO KOLXCO NEKOMMUTATIWNO I IMEET DELITELI NULQ. bOLEE TOGO, \TO KOLXCO IMEET NILXPOTENTY, SKAVEM, DLQ L@BYH i =6 j IMEEM e2ij = 0.

eSLI KOLXCO R KOMMUTATIWNO, TO WYPOLNQETSQ E]E SLEDU@]AQ AKSIOMA V5, POKAZYWA@]AQ, ^TO M(n; R) W DEJSTWITELXNOSTI QWLQETSQ ALGEBROJ NAD R.

V5 8x; y 2 M(n; R), 8® 2 R, (®x)y = ®(xy) = x(®y).

pUSTX Á : R ¡! S | GOMOMORFIZM KOLEC. tOGDA Á : M(n; R) ¡! M(n; S), (xij) 7!(Á(xij).

x 19. oBRATIMYE MATRICY I POLNAQ LINEJNAQ GRUPPA

|TA FORMULA OBOB]AETSQ I NA NEKOMMUTATIWNYJ SLU^AJ, NO, KONE^NO, OTWET POLU^AETSQ NESKOLXKO MENEE NAGLQDNYM. sLEDU@]AQ ZADA^A WZQTA IZ KNIGI77. eSTESTWENNO, TAM RASSMATRIWAETSQ TOLXKO SLU^AJ, KOGDA R = M(n; A) DLQ NEKOTOROGO KOMMUTATIWNOGO KOLXCA A, NO, KONE^NO, NI^EGO NE MENQETSQ I W OB]EM SLU^AE.

zADA^A. pREDPOLOVIM, ^TO x; y; z; w; x ¡ yw¡1z 2 R¤. pOKAVITE, ^TO TOGDA

77r.bELLMAN, wWEDENIE W TEORI@ MATRIC. | nAUKA, m., 1976, S.1{351, STR.114. zAMETIM, ^TO U bELLMANA PROPU]ENO USLOWIE x ¡ yw¡1z 2 GL(n; R).

(xy)o. tAKIM OBRAZOM, ^TOBY PROWERITX SOWPADENIE \TIH MATRIC, NAM NUVNO LI[X UBEDITXSQ W TOM, ^TO WSE IH SOOTWETSTWU@]IM MATRI^NYE \LEMENTY SOWPADA@T. w SAMOM DELE,

X X X

((xy)t)ij = ((xy)ji)o = (xjhyhi)o = yhio xojh = (yt)ih(xt)hj = (ytxt)ij;

GDE 1 · i · l, 1 · j · n, A WSE SUMMY BERUTSQ PO 1 · h · m.

tEOREMA. tRANSPONIROWANIE x 7!xt QWLQETSQ ANTIIZOMORFIZMOM KOLXCA

M(n; R) NA M(n; Ro).

sLEDSTWIE 1. dLQ L@BOGO KOLXCA M(n; R)o » M(n; Ro).

=

dOKAZATELXSTWO. w SAMOM DELE, PO TEOREME M(n; R) » M(n; Ro)o, OSTALOSX

=

E]E RAZ PEREJTI K PROTIWOPOLOVNYM KOLXCAM.

pUSTX TEPERX R KOMMUTATIWNO. w \TOM SLU^AE MY MOVEM OTOVDESTWITX Ro S R I RASSMATRIWATX TRANSPONIROWANIE KAK OTOBRAVENIE IZ M(m; n; R) W

M(n; m; R).

sLEDSTWIE 2. dLQ KOMMUTATIWNOGO KOLXCA R TRANSPONIROWANIE x 7!xt QW- LQETSQ ANTIAWTOMORFIZMOM KOLXCA M(n; R). w ^ASTNOSTI, W \TOM SLU^AE

M(n; R)o » M(n; R).

=

2. kONTRAGRADIENT. pOSMOTRIM, ^TO TRANSPONIROWANIE OZNA^AET S TO^KI ZRENIQ OBRATIMYH MATRIC.

sLEDSTWIE 3. eSLI x 2 GL(n; R) IMEEM (x¡1)t = (xt)¡1. w ^ASTNOSTI, DLQ

L@BOGO KOLXCA R IMEET MESTO IZOMORFIZM GL(n; Ro) » GL(n; R).

=

dOKAZATELXSTWO. pERWOE UTWERVDENIE SRAZU WYTEKAET IZ TEOREMY (TAK KAK ANTIAWTOMORFIZM PEREWOVIT e W e, ON AWTOMATI^ESKI PEREWODIT OBRATNYE W OBRATNYE). wTOROE UTWERVDENIE POLU^AETSQ TEPERX IZ TOGO, ^TO KAVDAQ GRUPPA ANTIIZOMORFNA SEBE POSREDSTWOM ANTIAWTOMORFIZMA inv : x 7!x¡1, KOMPOZICIQ DWUH ANTIIZOMORFIZMOW QWLQETSQ IZOMORFIZMOM.

pOLU^A@]IJSQ PRI \TOM IZOMORFIZM

trans ± inv : GL(n; R) ¡! GL(n; R)o ¡! GL(n; Ro)

NAZYWAETSQ KONTRAGRADIENTOM. oBRAZ x 2 GL(n; R) OTNOSITELXNO KONTRAGRADIENTA OBOZNA^AETSQ x¤ = (x¡1)t = (xt)¡1 I NAZYWAETSQ MATRICEJ, KONTRAGRADIENTNOJ K x. kAK BYLO OTME^ENO W DOKAZATELXSTWE POSLEDNEGO SLEDSTWIQ, (xy)¤ = x¤y¤. w SLU^AE KOMMUTATIWNOGO KOLXCA R KONTRAGRADIENT x 7!x¤ QWLQETSQ AWTOMORFIZMOM GL(n; R).

x 21. |RMITOWO SOPRQVENIE

w \TOM PARAGRAFE MY OPREDELIM ANTIAWTOMORFIZM M(n; R) WPREDPOLOVENII, ^TO

1. aNTIAWTOMORFIZMY KOLXCA R. pUSTX TEPERX : R ¡! R | ANTIAW-

TOMORFIZM KOLXCA R. iNYMI SLOWAMI, PREDPOLAGAETSQ, ^TO ® + ¯ = ® + ¯ I ®¯ = ¯ ®. kAK PRAWILO (NO NE WSEGDA!) \TOT ANTIAWTOMORFIZM PREDPOLAGAETSQ INWOL@CIEJ, T.E. ® = ®. wOT DWA TIPI^NYH PRIMERA: