UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika  1. stopnja Borut Zupan Ni£elno-neni£elni vzorci idempotentnih matrik Delo diplomskega seminarja Mentorica: izr. prof. dr. Polona Oblak Ljubljana, 2021

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika 1. stopnja

Borut Zupan

Ni£elno-neni£elni vzorci idempotentnih matrik Delo diplomskega seminarja

Mentorica: izr. prof. dr. Polona Oblak

Ljubljana, 2021

Kazalo

1. Uvod 4

2. Karakterizacija idempotentnih ni£elno-neni£elnih matrik 4

2.1. Poenostavitev problema 5

2.2. Karakterizacija binarnih idempotentnih matrik 13 3. ’tevilo moºnih neni£elnih elementov v idempotentnih ni£elno-neni£elnih

matrikah 18

Slovar strokovnih izrazov 27

Literatura 28

Ni£elno-neni£elni vzorci idempotentnih matrik Povzetek

V delu karakteriziramo n ×n idempotentne ni£elno-neni£elne matrike z elementi iz mnoºice {0,∗}. Da bi identicirali vse take matrike, ta problem prevedemo na iskanje n ×n binarnih idempotentnih matrik nad poljem R, ki ta problem re²ijo.

Nato dolo£imo najve£je ²tevilo moºnih neni£elnih elementov v idempotentni ni£elno- neni£elni matriki z danim rangom.

Idempotent zero-nonzero patterns Abstract

We rst characterize idempotent n×n zero-nonzero patterns with elements from {0,∗}. To identify these matrices, we convert this problem into characterizingn×n binary idempotent matrices over theR. Next we determine maximal possible number of nonzero entries in idempotent zero-nonzero pattern with a given minimum rank.

Math. Subj. Class. (2020): 15A03 15B99 05C50

Klju£ne besede: ni£elno-neni£elne matrike, idempotentnost, binarne matrike, rang

Keywords: zero-nonzero pattern, idempotence, binary matrix, rank

1. Uvod

Prve omembe matrik predznakov in njihovih uporab so se pojavile v knjigi Fo- undations of Economic Analysis [3], ki jo je leta 1947 izdal Nobelov nagrajenec iz ekonomije, P. Samuelson. V knjigi je omenil, da je nekatere probleme v ekonomiji treba re²evati glede na predznake elementov v matriki, neni£elne vrednosti pa so lahko poljubne. ’e bolj splo²ne matrike od matrik predznakov so ni£elno-neni£elne matrike, kjer nas zanima le vzorec ni£elnih in neni£elnih elementov. Motivacija za

²tudij ni£elno-neni£elnih matrik je naravna povezava med njimi in gra. Veliko pri- merov takih povezav je v knjigi A Combinatorial Approach to Matrix Theory and Its Applications [4], kjer s pomo£jo grafov dobimo nov pogled na teorijo matrik.

Naj bo F polje. Ozna£imo z M_n,k(F) mnoºico n×k matrik nad poljem F. V delu se bomo ukvarjali le s kvadratnimi matrikami iz mnoºice M_n,n(F), ki jo kraj²e ozna£imo z M_n(F).

Denicija 1.1. Matriko z elementi iz mnoºice {0,∗} imenujemo ni£elno-neni£elna matrika, kjer ∗ v matriki predstavlja poljuben neni£elen element iz poljaF.

Primer 1.2. Primer ni£elno-neni£elne matrike je

A =

⎡

⎣

0 ∗ ∗

∗ 0 ∗

∗ ∗ 0

⎤

⎦.

♢ Naj bo A = (a_ij) ni£elno-neni£elna matrika. Ozna£imo z Z_F(A) mnoºico matrik iz M_n,k(F) z vzorcem ni£el iz ni£elno-neni£elne matrike A, t.j.

Z_F(A) = {B = (b_ij)∈M_n,k(F)|b_ij = 0⇔a_ij = 0}.

Denicija 1.3. Binarna matrika je matrika, ki ima elemente iz mnoºice {0,1}. Mnoºico binarnih n×n matrik nad poljem Rozna£imo z M_n{0,1}.

V delu bomo obravnavali problem idempotentnosti ni£elno-neni£elnih matrik. Po- kazali bomo, da jih lahko karakteriziramo s pomo£jo usmerjenih grafov, v katerih so sprehodi med istim za£etnim in kon£nim vozli²£em razli£nih dolºin. Nato bomo dokazali, da obstaja povezava med idempotentnimi ni£elno-neni£elnimi matrikami in binarnimi idempotentnimi matrikami iz mnoºice M_n{0,1}. Nazadnje si ogle- damo, koliko neni£elnih elementov je lahko v idempotentni ni£elno-neni£elni matriki s podanim rangom.

2. Karakterizacija idempotentnih ni£elno-neni£elnih matrik V tem poglavju se bomo seznanili z ni£elno-neni£elnimi matrikami in njihovo pove- zavo s teorijo grafov. Podrobneje si bomo ogledali prvi problem, t.j. karakterizacijo kvadratnih idempotentnih ni£elno-neni£elnih matrik. Pri tem bomo sledili [2].

Problem 1. Karakterizirajmo kvadratne ni£elno-neni£elne matrike A, za katere ve- lja, da je B² ∈Z_F(A), kadar je B ∈Z_F(A).

Ni£elno-neni£elne matrike, ki imajo lastnost iz problema 1, imenujemo idempo- tentne ni£elno-neni£elne matrike nad poljem F. Mnoºico idempotentnih ni£elno- neni£elnih matrik A∈Mn(F) ozna£imo z Ωn(F).

2.1. Poenostavitev problema. Ozna£imo z A(i, j) element vi-ti vrstici in j-tem stolpcu matrikeA. Preden pridemo do glavnih rezultatov, moramo najprej dokazati nekaj lem.

Lema 2.1. Naj ima poljeF vsaj tri elemente in naj boA∈Ωn(F). ƒe jeA(i, j) =∗ in A(j, k) =∗, potem je A(i, k) =∗.

Dokaz. Poglejmo si dva primera.

Za primer, ko je j enaki alik, lema 2.1 velja trivialno.

V drugem primeruj ni enakiinj ni enakk. Naj boB ∈Z_F(A). ƒe pokaºemo, da B²(i, k)̸= 0, potem sledi, da B(i, k)̸= 0, ker je A ∈Ω_n(F). Najprej vsa neni£elna

²tevila v B zamenjajmo z 1, razen ²tevila B(i, j) in to novo matriko ozna£imo s C. Ker je B ∈ Z_F(A), je tudi C ∈ Z_F(A). Element C²(i, k) dobimo z matri£nim mnoºenjem matrike C same s sabo, torej

C²(i, k) = ∑︂

l

C(i, l)C(l, k) =C(i, j)C(j, k) +∑︂

l̸=j

C(i, l)C(l, k)

=C(i, j) +∑︂

l̸=j

C(i, l)C(l, k) Po deniciji matrike C je vsota ∑︁

l̸=j

C(i, l)C(l, k) ≥ 0. Ker ima polje F vsaj tri elemente, ima vsaj dva neni£elna elementa. Torej lahko sklepamo, da obstaja ne- ni£elen element C(i, j) v F, da je C²(i, k) ̸= 0. Torej je tudi C(i, k) ̸= 0. Zato

A(i, k) =∗. □

Matrikam z lastnostjo iz leme 2.1 pravimo, da so tranzitivne.

Lema 2.1 ne deluje za primer, ko ima polje le dva elementa.

Primer 2.2. Naj boAmatrika iz primera 1.2. ƒe vzamemo poljeF za polje z dvema elementoma Z2, potem je edina matrika v Z_Z2(A) tista, v kateri ∗ zamenjamo z 1. Matriki

A =

⎡

⎣

0 ∗ ∗

∗ 0 ∗

∗ ∗ 0

⎤

⎦ priredimo matriko

B =

⎡

⎣

0 1 1 1 0 1 1 1 0

⎤

⎦∈Z_Z2(A).

Po kratkem izra£unu dobimo, da jeB idempotentna. Zato jeA∈Ω₃(Z2). V matriki A sta elementa A(i, j) = A(j, i) = ∗, ko je i razli£en od j. Po lemi 2.1 bi moral element A(i, i) biti neni£elen, vendarA(i, i) = 0.

Matrika A ni idempotentna nad vsemi moºnimi polji. Za protiprimer lahko vza- memo polje Z3, kjer je kvadrat matrike B enak

B² =

⎡

⎣

2 1 1 1 2 1 1 1 2

⎤

⎦.

Elementi na diagonali so neni£elni, zato B² ∈/ Z_Z3(A). Sledi, da ni£elno-neni£elna

matrika A ni v mnoºici Ω₃(Z3). ♢

Za nadaljnjo razpravo si moramo ogledati ²e nekaj denicij in oznak iz teorije grafov.

Denicija 2.3. Usmerjen graf G je urejen par G = (V, E), kjer je V neprazna mnoºica to£k oziroma vozli²£, E pa mnoºica usmerjenih povezav (v_i, v_j).

Povezavo od vozli²£a i do vozli²£a j ozna£imo z oznako i→j ali (i, j). Denicija 2.4. Naj bo G usmerjen graf. Zaporedje vozli²£ in povezav

v₀e₁v₁e₂v₂...v_k−1e_kv_k,

kjer jee_i povezava med to£kamavi−1 inv_i,i∈ {1, ..., k}, imenujemo sprehod dolºine k.

(1) Dolºina sprehoda je ²tevilo povezav na sprehodu.

(2) Sprehod je enostaven, £e so vse uporabljene povezave razli£ne.

(3) Enostaven sprehod je pot, £e so vsa obiskana vozli²£a razli£na.

(4) Cikel je sklenjena pot, torej pot, kjer sta za£etno in kon£no vozli²£e enaka.

Z oznako i−→^d j ozna£imo sprehod od i doj dolºine d.

Naj boA∈Mn(F)ni£elno-neni£elna matrika. Z D(A) = (V(A), E(A))ozna£imo usmerjeni graf matrike A, kjer je V(A) = {1,2, ..., n} mnoºica vozli²£. Povezava i→j je v E(A) natanko tedaj, ko je A(i, j)̸= 0.

Matrike in gra so med sabo povezani na ve£ razli£nih na£inov. Graf lahko pred- stavimo z matriko sosednosti ali z inciden£no matriko in iz matrike lahko dobimo graf na ºe prej opisan na£in. Lastnosti grafov lahko prepoznamo iz lastnosti pri- padajo£ih matrik in obratno. Za primer lahko vzamemo lemo 2.1. Dokazali smo, da £e sta A(i, j) = A(j, k) = ∗, potem je A(i, k) = ∗. Kaj bi ta lastnost povedala o grafu D(A)? Pove, da £e obstaja sprehod dolºine 2 od vozli²£a i do vozli²£a k, potem obstaja tudi sprehod dolºine 1 oz. povezava med istim za£etnim in kon£nim vozli²£em. Tako tudi deniramo tranzitivnost grafa. Pokaºimo to ²e na primeru.

Primer 2.5. Ni£elno-neni£elna matrika A=

⎡

⎣

0 ∗ ∗ 0 ∗ ∗ 0 0 0

⎤

⎦ porodi graf D(A), prikazan na sliki 1.

1

2 3

Slika 1. Graf D(A) matrikeA Opazimo, da je D(A)tranzitiven graf, ker

• obstajata povezavi 1→2 in2→3 in tudi povezava1→3,

• obstajata povezavi 1→2 in2→2 in tudi povezava1→2,

• obstajata povezavi 2→2 in2→3 in tudi povezava2→3.

• obstajata povezavi 2→2 in2→2 in tudi povezava2→2.

Drugih sprehodov dolºine 2 ni. ♢

S pomo£jo grafov lahko dokaºemo naslednjo lemo.

Lema 2.6. Naj bo Y ∈M_n(F) strogo zgornje trikotna matrika. Potem je Y nilpo- tentna matrika.

Dokaz. Naj bo Y strogo zgornje trikotna matrika in D(Y)njen usmerjeni graf. Ker je Y strogo zgornje trikotna matrika, povezava i→j obstaja natanko tedaj, ko jei strogo manj²i odj. Zato vD(Y)ni nobenih ciklov. Zaradi tega v D(Y) ne obstaja sprehod dolºine ve£je ali enake n. Produkt Y(i, i₁)Y(i₁, i₂)· · ·Y(in−1, j) iz vsote

Yⁿ(i, j) = ∑︂

1≤i1,...,ik−1≤n

Y(i, i₁)Y(i₁, i₂)· · ·Y(in−1, j)

predstavlja sprehod dolºine n od i do j. Ker takih sprehodov ni, je Yⁿ = 0, kar

pomeni, da je Y nilpotentna matrika. □

Dokaºimo nekaj lastnosti grafov, ki jih dobimo s pomo£jo matrik A ∈Ω_n(F). Lema 2.7. Naj ima F vsaj tri elemente in naj bo A ∈ Ω_n(F). ƒe je A(i, j) = 0, potem v grafu D(A) ne obstaja sprehod od vozli²£a i do vozli²£a j.

Dokaz. Recimo, da obstaja sprehod dolºinek odidoj. Ker jeA(i, j) = 0, povezave (i, j)vD(A)ni. Torej jek ≥2in obstajajo vozli²£ai₁, i₂, ..., ik−1, da veljaA(i, i₁) = A(i₁, i₂) = ... = A(ik−1, j) = ∗. Sedaj uporabimo lemo 2.1 za elementa A(i, i₁) in A(i₁, i₂). Ker sta oba elementa neni£elna, je tudi element A(i, i₂) neni£elen. ’e enkrat uporabimo isto lemo, tokrat na elementih A(i, i₂) in A(i₂, i₃). Ker sta spet oba neni£elna, je neni£elen tudi element A(i, i₃). ƒe to ponavljamo (k −1)-krat, dobimo A(i, j) = ∗, kar je v protislovju s predpostavko, da je element A(i, j) enak

0. Zato ne obstaja sprehod med i inj v D(A). □

Ponovno smo uporabili predpostavko, da ima polje vsaj tri elemente. Kaj pa matrike nad poljem z dvema elementoma?

Primer 2.8. Naj bo A matrika iz primera 1.2, torej matrika A=

⎡

⎣

0 ∗ ∗

∗ 0 ∗

∗ ∗ 0

⎤

⎦∈Ω3(Z²).

Opazimo, da je A(2,2) = 0. Torej ni zanke na vozli²£u 2. Vendar sta elementa A(2,1) in A(1,2) enaka ∗, zato v D(A) obstaja sprehod dolºine 2 od vozli²£a 2 do vozli²£a 2. Torej lema 2.7 ne velja za matrike nadZ2. ♢ V lemi 2.7 smo pokazali, da £e je A(i, j) = 0, potem ne obstaja sprehod med iin j v D(A). Kaj pa £e je element A(i, j) neni£elen? To nam bo pokazala naslednja lema.

Lema 2.9. Naj bo A∈Ω_n(F). ƒe je A(i, j) =∗, potem za vsako naravno ²tevilo k obstaja vsaj en sprehod dolºine k od vozli²£a i do vozli²£a j v D(A).

Dokaz. ƒe jek = 1, potem lema 2.9 velja trivialno, ker jeA(i, j) =∗in zato obstaja sprehod dolºine 1od i doj.

Za k ≥ 2 dokaºimo z indukcijo. Najprej si poglejmo, £e lema 2.9 velja za bazo, torej k= 2. Ker jeA∈Ωn(F), iz B(i, j)̸= 0 sledi B²(i, j)̸= 0 za vsak B ∈ZF(A). Ker element

B²(i, j) =

n

∑︂

l=1

B(i, l)B(l, j)

ni enak 0 lahko sklepamo, da za nek l velja B(i, l) = B(l, j) = ∗. To je sprehod dolºine dve od i doj. Torej lema 2.9 velja za k = 2.

Predpostavimo, da lema 2.9 velja za k =m≥3. Naj bo i→i₁ →i₂ →...→im−1 →j

sprehod dolºine m od i do j v D(A). Potem je A(i_m−1, j) = ∗. Ker lema velja za k = 2, obstaja vsaj en sprehod dolºine 2 od i_m−1 do j v grafu D(A). Pa naj bo im−1 → i_m → j tak sprehod. Naslednji korak je zdruºitev dveh sprehodov v en sprehod od i doj v D(A)oblike

i→i₁ →i₂ →...→im−1 →i_m →j,

ki je dolºine m+ 1. Zato lema 2.9 velja zak =m+ 1. □ Naslednje naravno vpra²anje po lemi 2.9 je vpra²anje o enoli£nosti takih spreho- dov, t.j. ali je v D(A)ve£ sprehodov dolºine k ali je morebiti samo eden.

Trditev 2.10. Naj ima F vsaj tri elemente in naj boA∈Ω_n(F). ƒe jeA(i, j) = ∗, potem za vsako naravno ²tevilo k obstaja natanko en sprehod dolºine k od vozli²£a i do vozli²£a j v D(A).

Dokaz. Ozna£imo s k dolºino sprehoda. Za k = 1 lema velja, ker obstaja natanko ena povezava od i do j.

Pokaºimo najprej, da lema velja za k = 2. Po lemi 2.9 obstaja vsaj en sprehod dolºine 2 od i do j. Dokazovanja se lotimo tako, da predpostavimo, da obstajata vsaj dva sprehoda dolºine2, nato konstruitamo matrikoB ∈Z_F(A), za katero velja B²(i, j) = 0, kar nas bo pripeljalo do protislovja s tem, da sta B(i, j) in B²(i, j) neni£elna. Lo£imo na dva primera.

(1) Naj bo i=j. V tem primeru je A(i, i) =∗ in zato ima graf D(A)zanko. ƒe se sprehodimo dvakrat po zanki, dobimo prvi sprehod dolºine 2od i doi. Denimo, da obstaja vsaj ²e en sprehod dolºine 2 od i do i. Ker obstajata dva sprehoda, obstaja i₁, ki ni enaki, da velja A(i₁, i) =A(i, i₁) = ∗. ElementB²(i, i)se izra£una na naslednji na£in:

(1) B²(i, i) =B(i, i₁)B(i₁, i) +∑︂

l̸=i1

B(i, l)B(l, i).

Najprej pokaºimo, da obstajajo vrednosti vseh neni£elnih elementov matrikeBrazen B(i, i₁) v F, da je vsota∑︁

l̸=i1B(i, l)B(l, i) razli£na od 0. Lo£imo dva primera.

(1a)Prvi£ si poglejmo primer, koA(i, l) = 0 aliA(l, i) = 0za vsakl, ki je razli£en od i ini₁. Takrat je

∑︂

l̸=i1

B(i, l)B(l, i) = B²(i, i).

Naj bo C ∈ Z_F(A) matrika, ki ima vse neni£elne elemente enake 1 razen element C(i, i₁) naj bo enak B(i, i₁). Potem velja

∑︂

l̸=i1

C(i, l)C(l, i) = C²(i, i) = 1.

Ker je C ∈Z_F(A), velja

∑︂

l̸=i1

B(i, l)B(l, i)̸= 0.

(1b) V drugem primeru obstaja i₂, ki je razli£en od i in i₁, da je A(i, i₂) = A(i₂, i) = ∗. V tem primeru velja enakost

∑︂

l̸=i₁

B(i, l)B(l, i) = B(i, i₂)B(i₂, i) + ∑︂

l̸=i₁,i2

B(i, l)B(l, i).

Naj bo C ∈ Z_F(A) matrika, ki ima vse neni£elne elemente enake 1 razen element C(i, i₁) naj bo enak B(i, i₁) in element C(i, i₂) naj bo enak B(i, i₂). Ker ima F vsaj dva neni£elna elementa, potem ne glede na vrednost vsote∑︁

l̸=i₁,i2C(i, l)C(l, i) obstaja neni£elni element B(i, i₂), da velja

∑︂

l̸=i1

C(i, l)C(l, i)̸= 0.

Ker je C ∈Z_F(A), velja

∑︂

l̸=i1

B(i, l)B(l, i)̸= 0.

Naj bo element

B(i, i₁) =− (︄

∑︂

l̸=i1

B(i, l)B(l, j) )︄

·B(j₁, j)⁻¹ ̸= 0.

Ta element vstavimo v enakost (1) in dobimo matriko B ∈ Z_F(A) za katero velja, da je B²(i, i)enak 0.

(2)V drugem primeru gledamo izvendiagonalne elemente, torejA(i, j), kjeri̸=j. Denimo, da obstajata vsaj dva sprehoda dolºine 2 od i doj. Torej obstajata j₁ in j₂, kjerj₁ ̸=j₂ in j₁ ̸=j, tako da A(i, j₁) =A(j₁, j) =A(i, j₂) =A(j₂, j) = ∗. Velja (2) B²(i, j) =B(i, j1)B(j1, j) +∑︂

l̸=j₁

B(i, l)B(l, j).

Najprej pokaºimo, da obstajajo vrednosti vseh neni£elnih elementov matrikeBrazen B(i, j₁)v F, da velja enakost

∑︂

l̸=j1

B(i, l)B(l, j) =B(i, j₂)B(j₂, j) + ∑︂

l̸=j1,j2

B(i, l)B(l, j)̸= 0.

Lo£imo na dva primera.

(2a) Prvi£, £e je j₂ = j. Naj bo C ∈ Z_F(A) matrika, ki ima vse neni£elne elemente enake 1 razen element C(i, j₁) naj bo enak B(i, j₁) in element C(j₂, j) naj bo enak B(j₂, j). Ker ima F po predpostavki vsaj tri elemente, ima vsaj dva neni£elna elementa. Zato obstaja neni£elna vrednost B(j₂, j) v F, tako da velja

∑︁

l̸=j1C(i, l)C(l, j)̸= 0. Ker je C∈Z_F(A), velja

∑︂

l̸=j₁

B(i, l)B(l, j)̸= 0.

(2b)Drugi£, £e j₂ ̸=j. Naj boC ∈Z_F(A) matrika, ki ima vse neni£elne elemente enake 1 razen element C(i, j1) naj bo enak B(i, j1) in elementC(i, j2) naj bo enak B(i, j2). Polje F ima po predpostavki vsaj dva neni£elna elementa, zato obstaja neni£elna vrednost B(i, j₂) v F, tako da velja ∑︁

l̸=j₁C(i, l)C(l, j) ̸= 0. Ker je C ∈ Z_F(A), velja

∑︂

l̸=j1

B(i, l)B(l, j)̸= 0.

Pokazali smo, da je vsota ∑︁

l̸=j1B(i, l)B(l, j)razli£na od 0. Naj bo element B(i, j₁) = −

(︄

∑︂

l̸=j1

B(i, l)B(l, j) )︄

·B(j₁, j)⁻¹ ̸= 0.

Ta element vstavimo v enakost (2) in dobimo matriko B ∈ Z_F(A) za katero velja, da jeB²(i, j)enak0. Ker jeA∈Ω_n(F), je tudiB(i, j) = 0. Pri²li smo v protislovje s tem, da je element A(i, j) neni£elen. Zato obstaja natanko en sprehod dolºine 2 od i doj.

Dokazati moramo ²e, da lema velja za k ≥3. Po lemi 2.9 za vsakk ∈ N obstaja vsaj en sprehod dolºine k od i doj v D(A). Pa recimo, da za nek k0 ≥3obstajata vsaj dva razli£na sprehoda dolºine k₀ od idoj. Recimo, da je prvii→i₁ → · · · → i_k0−1 →j in drugii→ j₁ → · · · → j_k0−1 →j. Ker sta sprehoda razli£na, obstajata i^′ ∈ {i₁, . . . , i_k0−1}in j^′ ∈ {j₁, . . . , j_k0−1}, ki sta razli£na. Opazimo lahko, da

A(i, i₁) = · · ·=A(i_k0−1, j) = ∗ in

A(i, j₁) =· · ·=A(j_k0−1, j) = ∗.

ƒe nekajkrat uporabimo lemo 2.1, dobimo, da sta elementa A(i, i^′) = A(i^′, j) = ∗ in prav tako sta elementa A(i, j^′) =A(j^′, j) =∗. Iz tega sledi, da sta i→i^′ →j in i→j^′ →j dva razli£na sprehoda dolºine 2od i do j v D(A), kar je v protislovju s tem, da obstaja samo en sprehod dolºine 2 od i do j. Zato za vsak k ≥ 3 obstaja

natanko en sprehod dolºine k od i doj v D(A). □

Trditev 2.10 ne deluje za matrike nad poljem Z2.

Primer 2.11. Naj bo F =Z2 in A matrika iz primera 1.2. Njen graf je prikazan na sliki 2.

1

2 3

Slika 2. Graf D(A) matrikeA∈Ω₃(Z2)

V tej matriki je A(1,2) = ∗. Ampak 1 → 2 → 1 → 2 in 1 → 2 → 3 → 2 sta dva razli£na sprehoda dolºine 3od vozli²£a 1do vozli²£a 2 v D(A). ♢ Lema 2.12. Naj bo Y ∈M_n(F) idempotentna matrika. Potem je Y^k =Y za vsak k ∈N.

Dokaz. Dokazujemo z indukcijo. Za k = 1 lema 2.12 velja trivialno. Naj lema 2.12 velja za k ≥1. Dokazujemo, da velja tudi za k+ 1. Velja

Y^k+1 =Y ·Y^k =Y ·Y =Y².

Ker je Y idempotentna, je Y² =Y. Torej Y^k+1 =Y. □

Naj bo Y ∈ M_n(F). Po lemi 2.12 je Y^k =Y za vsak k ∈N. Ali to velja tudi za idempotentne ni£elno-neni£elne matrike?

Posledica 2.13. Naj bo A∈Ω_n(F). Potem za vsako naravno ²tevilo k velja, da je B^k∈Z_F(A), £e je B ∈Z_F(A).

Dokaz. Glede na ²tevilo elementov v polju F lo£imo dva primera.

(1) Polje F ima samo dva elementa. Torej F = Z2, v katerem obstaja samo en neni£elni element 1. Velja, da jeA(i, j) = ∗natanko tedaj, ko jeB(i, j) = 1. Iz tega sledi, da obstaja samo ena matrika B v mnoºiciZ_Z2(A), za katero veljaB² =B. Po lemi 2.12 velja, da je B^k enakB za vsak k ∈N.

(2) PoljeF ima vsaj tri elemente. Za vsakB ∈Z_F(A)in za vsako naravno ²tevilo k veljaD(A) = D(B). Velja, da je

B^k(i, j) = ∑︂

1≤i1,...,ik−1≤n

B(i, i₁)B(i₁, i₂)· · ·B(ik−1, j).

ƒe je produkt B(i, i₁)B(i₁, i₂)· · ·B(ik−1, j)razli£en od 0, potem je B(i, i₁)̸= 0, B(i₁, i₂)̸= 0,. . ., B(ik−1, j)̸= 0. To pomeni, da v grafu D(B) obstaja sprehod

i→i₁ → · · · →ik−1 →j

dolºine k od i do j. Lahko si mislimo, da produkt B(i, i₁)B(i₁, i₂)· · ·B(ik−1, j) predstavlja sprehod dolºine k odi do j v grafuD(B). Torej, £e velja

B(i, i₁)B(i₁, i₂)· · ·B(ik−1, j)̸= 0,

potem obstaja sprehod dolºinekodidoj po povezavahi→i₁,i₁ →i₂,. . .,ik−1 →j. Po podobnih sklepih lahko ugotovimo, £e velja

B(i, i1)B(i1, i2)· · ·B(ik−1, j) = 0,

potem ne obstaja sprehod dolºine k od i do j po povezavah i → i1, i1 → i2,. . ., ik−1 → j. ƒe je B(i, j) = 0, po lemi 2.7 ne obstaja sprehod dolºine k od i do j. TorejB^k(i, j) = 0. ƒe jeB(i, j)̸= 0, potem po trditvi 2.10 sledi, da obstaja natanko en sprehod dolºine k od ido j. Torej B^k(i, j)̸= 0. Sledi, da velja B^k(i, j)∈Z_F(A)

za vsak k∈N. □

S tem smo pokazali, da iz idempotentnih ni£elno-neni£elnih matrik dobimo usmer- jene grafe, v katerih so sprehodi z istim za£etnim in kon£nim vozli²£em razli£nih dolºin. S Θ(n) ozna£imo mnoºico usmerjenih grafov na n vozli²£ih, ki imajo to lastnost. Te grafe je raziskoval Xingzhi Zhan [1], ki je podal problem 1.

Problem karakterizacije idempotentnih ni£elno-neni£elnih matrik ²e bolj poeno- stavimo. Naslednji izrek bo povezal idempotentne ni£elno-neni£elne matrike A z idempotentnimi matrikami A^′ ∈M_n{0,1}.

Izrek 2.14. Naj bo F polje z vsaj tremi elementi. Naj bo A ∈ M_n(F) ni£elno- neni£elna matrika in A^′ ∈ Z_F(A) binarna matrika. Potem je A idempotentna ni£elno-neni£elna matrika natanko tedaj, ko je A^′ idempotentna.

Dokaz. Naj bo A ∈ Ω_n(F). Ozna£imo z A^′ ∈ M_n{0,1} matriko, ki jo dobimo iz ni£elno-neni£elne matrike A tako, da vse ∗ zamenjamo z 1. Velja, da je graf D(A) enak grafu D(A^′), ker imata na istih mestih neni£elne elemente. Pokazati moramo, da je matrika A^′ idempotentna. Torej, £e je A^′(i, j) = 0, potem je tudiA^′2(i, j) = 0. To velja po lemi 2.7. Po trditvi 2.10 pa iz A^′(i, j) = 1 slediA^′2(i, j) = 1, ker obstaja

natanko en sprehod dolºine 2 od vozli²£a i do vozli²£a j. Dokazali smo implikacijo v desno smer.

Dokaºimo ²e implikacijo v levo. Naj boA^′ ∈M_n{0,1}idempotentna. Zanjo velja A^′(i, j) =A^′2(i, j) =

n

∑︂

k=1

A^′(i, k)A^′(k, j).

ƒe je A^′(i, j) = 0, potem je produkt A^′(i, k)A^′(k, j) enak 0 za vsak k = 1, . . . , n. Kaj predstavlja produkt A^′(i, k)A^′(k, j)? A^′(i, k)predstavlja povezavo od vozli²£a i do vozli²£ak, torej produktA^′(i, k)A^′(k, j)predstavlja sprehod dolºine2od vozli²£a i do vozli²£a j. ƒe je ta produkt enak 0 za vsak k = 1, . . . , n, potem ne obstaja sprehod dolºine2odidojv grafuD(A^′). S podobnimi sklepi lahko ugotovimo, da £e je A^′(i, j) = 1, potem obstaja natanko en sprehod dolºine2odidoj v grafuD(A^′). Ozna£imo zAni£elno-neni£elno matriko pridobljeno izA^′ tako, da vse1zamenjamo z ∗. Ker je D(A^′) = D(A), lahko sklepamo, da za vsak B ∈ Z_F(A) iz B(i, j) = 0 sledi B²(i, j) = 0 in iz B(i, j)̸= 0 sledi B²(i, j)̸= 0. Zato jeA∈Ω_n(F). □ Izrek ima enako pomanjkljivost kot nekatere prej²nje leme. Izrek namre£ ne deluje za polje Z2.

Primer 2.15. Vzamemo matriko Aiz primera 1.2. Matrika Aje v mnoºici Ω₃(Z²). Po izreku 2.14 ji priredimo matriko

A^′ =

⎡

⎣

0 1 1 1 0 1 1 1 0

⎤

⎦∈M₃{0,1},

ki ni idempotentna, kot smo videli v primeru 2.2. ♢

Primer 2.16. Eden bolj o£itnih primerov idempotentnih ni£elno-neni£elnih matrik je matrika

A_In =

⎡

⎣

∗ 0 0 0 ∗ 0 0 0 ∗

⎤

⎦ Po izreku 2.14 matriki AIn priredimo matriko

⎡

⎣

1 0 0 0 1 0 0 0 1

⎤

⎦=I_n,

ki je idempotentna. Zato je tudi A_In idempotentna ni£elno-neni£elna matrika.

Primer matrik, ki niso idempotentne so nilpotentne matrike N^′, ker za njih velja, da je (N^′)^k = 0_n za nek k ∈ N. Zato tudi matrike N, ki jih dobimo iz N^′, niso v mnoºici Ω_n(F). Konkretni primer je matrika

N =

⎡

⎣

0 ∗ ∗ 0 0 ∗ 0 0 0

⎤

⎦. Priredimo ji matriko

N^′ =

⎡

⎣

0 1 1 0 0 1 0 0 0

⎤

⎦.

ƒe matriko N^′ kvadriramo, dobimo matriko (N^′)² =

⎡

⎣

0 0 1 0 0 0 0 0 0

⎤

⎦.

Ker (N^′)² ̸=N^′, po izreku 2.14 velja, da matrikaN ni v mnoºici Ω3(F). ♢ 2.2. Karakterizacija binarnih idempotentnih matrik. V prej²njem podraz- delku smo problem karakterizacije matrik A ∈ Ω_n(F) poenostavili na problem ka- rakterizacije idempotentnih matrik A^′ ∈ M_n{0,1}. V tem podrazdelku se bomo zato posvetili karakterizaciji binarnih idempotentnih matrik.

Problem 2. Karakterizirajmo idempotentne matrike A^′ ∈M_n{0,1}. Najprej poglejmo nekaj denicij.

Denicija 2.17. Matriki A in B iz M_n(F) sta podobni, £e obstaja obrnljiva n×n matrika P, da veljaB =P⁻¹AP.

ƒe je matrika P permutacijska matrika, potem re£emo, da sta A in B permuta- cijsko podobni.

Denicija 2.18. Matrika A ∈ Mn(F) je razcepna, £e obstaja n×n permutacijska matrika P, da velja

P^TAP =

[︃X Y 0 Z

]︃

,

kjer sta X inZ kvadratni matriki. ƒe matrika A ni razcepna, je nerazcepna.

ƒe bi permutacijsko podobnost, opisano v deniciji 2.18, uporabili ²e naprej na diagonalnih blokih matrike P^TAP, bi na koncu pri²li do blo£no zgornje trikotne matrike, ki bi na diagonali imela le nerazcepne matrike. Taki obliki matrike pravimo Frobeniusova normalna oblika.

Trditev 2.19. Razcepna matrika A je permutacijsko podobna njeni Frobeniusovi normalni obliki

⎡

⎢

⎢

⎣

A₁₁ A₁₂ · · · A_1p 0 A₂₂ · · · A_2p ... ... ... ...

0 0 · · · A_pp

⎤

⎥

⎥

⎦ ,

kjer je vsak blok A_ii nerazcepna matrika.

Kako preverimo, ali je neka matrika nerazcepna ali razcepna? Obstaja ve£ na£i- nov, ki pa so odvisni od posebne strukture matrike, npr. nenegativnost, v Hessen- bergove oblike itd.

Denicija 2.20. Naj bo D = (V, E) usmerjen graf. ƒe za vsak u, v ∈ V obstaja usmerjena pot od u do v in od v do u, potem takemu grafu re£emo, da je krepko povezan.

Trditev 2.21. Matrika Y ∈M_n(F)je nerazcepna natanko tedaj, ko je njen usmer- jeni graf D(Y) krepko povezan.

Dokaz. Naj bo Y ∈ M_n(F) matrika in naj bo D(Y) = (V, E) njen usmerjeni graf.

Recimo, da jeY razcepna matrika. Ker jeY permutacijsko podobna zgornje trikotni matriki, sledi, da lahko mnoºico vozli²£ V razdelimo na dve disjuntkni mnoºici

V₁ in V₂ tako, da ni nobene usmerjene povezave od vozli²£ iz V₁ do vozli²£ iz V₂. Ampak graf take matrike ni krepko povezan, ker ne obstaja usmerjena pot od vozli²£a u₁ ∈V₁ do vozli²£a u₂ ∈V₂.

Recimo, da D(Y) ni krepko povezan graf. Potem obstajata dve razli£ni vozli²£i u in v, med katerima ne obstaja usmerjena pot od u do v. Deniramo mnoºico W₁, v kateri so vsa vozli²£a, za katera obstaja usmerjena pot od u do teh vozli²£.

Mnoºica W2 je denirana podobno, le da obstaja usmerjena pot do v od vozli²£ iz W2. Mnoºici W1 inW2 sta neprazni in disjunktni. Naj bo W3 mnoºica vozli²£, ki ne spadajo v W₁ in W₂. Sedaj pa permutiramo vrstice matrike Y tako, da so vrstice, ki ustrezajo vozli²£em iz W₂ prve, naslednje so vrstice, ki ustrezajo vozli²£em izW₃ in zadnje so vrstice, ki ustrezajo vozli²£em iz W₁. Enako premutiramo tudi stolpce matrike Y. Dobimo matriko oblike

⎡

⎣

W₂ W₃ W₁ W₂ X₁₁ X₁₂ X₁₃ W₃ X₂₁ X₂₂ X₂₃ W₁ X₃₁ X₃₂ X₃₃

⎤

⎦.

Ker ne obstaja usmerjena pot odudov, potem tudi ne obstaja povezava od vozli²£a iz W₁ do vozli²£a iz W₂. Ker so v W₃ taka vozli²£a, ki ne spadajo ne v W₁ kot tudi ne v W₂, ne obstaja povezava med vsakim vozli²£emcizW₃ in vsakim vozli²£emv₂ iz W₂. ƒe bi namre£ obstajala, potem bi vozli²£e c pripadalo W₂. Zato je X₃₁ = 0 in X21 = 0. Dobimo matriko

⎡

⎣

W₂ W₃ W₁ W₂ X₁₁ X₁₂ X₁₃ W₃ 0 X₂₂ X₂₃ W₁ 0 X₃₂ X₃₃

⎤

⎦,

ki pa je blo£no zgornje trikotna, kar pomeni, da je Y razcepna. □ Trditev pravi, da £e ºelimo nerazcepne matrike A^′ ∈ M_n{0,1}, moramo najti krepko povezane grafe D(A^′). Omejili se bomo na matrike A^′ iz mnoºice

Γ(n) ={A^′ ∈M_n{0,1}|(A^′)^k ∈M_n{0,1}za vsak k ∈N} ⊆M_n{0,1}.

Ker za matriko A^′ ∈ Γ(n) velja, da je (A^′)^k ∈ M_n{0,1} za vsak k ∈ N, je graf D(A^′) ∈ Θ(n). V naslednji trditvi bomo pokazali, kak²en vzorec imajo matrike iz mnoºice Γ(n).

Trditev 2.22. Naj bo A^′ ∈ Γ(n), kjer n ≥ 2. Matrika A^′ je nerazcepna natanko tedaj, ko je A^′ permutacijsko podobna matriki

Cn =

⎡

⎢

⎢

⎣

0 1 · · · 0 ... ... ... ...

0 · · · 0 1 1 0 · · · 0

⎤

⎥

⎥

⎦ .

Najprej dokaºimo naslednjo lemo.

Lema 2.23. Naj bo D ∈ Θ(n), kjer n ≥ 2. Potem je D krepko povezan natanko tedaj, ko je D cikel.

Dokaz. Implikacija v levo je preprosta, ker je vsak cikel krepko povezan. Zato mo- ramo dokazati samo implikacijo v desno.

Naj bo D ∈ Θ(n) krepko povezan graf. Da je D cikel, je dovolj dokazati, da je izhodna stopnja vsakega vozli²£a grafa D enaka 1. Ker je D krepko povezan, je izhodna stopnja vsaj 1. Dokazujemo s protislovjem. Recimo, da je izhodna stopnja nekega vozli²£a i grafa D vsaj 2. Torej ima vsaj dve razli£ni usmerjeni povezavi, kjer je i za£etno vozli²£e. Recimo da sta ti dve povezavi i → j in i → k. Lo£imo dva primera.

(1) Naj bo i = j ali i = k, torej graf D ima zanko. Brez ²kode za splo²nost vzemimo, da je i = j. Ker je D krepko povezan, obstaja pot k −→^dki i. Dobili smo dva sprehoda od ido i in siceri→k −→^dki i ter i→i→. . .→i, ki sta enako dolga.

To pa je v protislovju s tem, da je D∈Θ(n). Podobno velja za i=k.

(2) Naj bo j ̸=i in k ̸=i. Ker je D krepko povezan, obstaja pot j −→^dji i in pot k −→^dki i. Naj bo d= lcm(d_ji+ 1, d_ki+ 1) najmanj²i skupni ve£kratnik ²tevild_ji+ 1 in d_ki+ 1. Potem smo spet dobili dva razli£na sprehoda od i do i z dolºino d:

S1 :i→j −→^dji i→. . .→i→j −→^dji i S₂ :i→k −→^dki i→. . .→i→k −→^dki i,

kjer je _dji^d₊₁ ciklov i → j −→^dji i v S₁ in _dki^d₊₁ ciklov i → k −→^dki i v S₂. To je v

protislovju s tem, da je D∈Θ(n). □

Dokaz trditve 2.22. Po trditvi 2.21, je matrika A^′ nerazcepna natanko tedaj, ko je D(A^′)krepko povezan. Uporabimo lemo 2.23 in dokaz je zaklju£en. □ Zakaj potrebujemo nerazcepnost matrik v tem delu? Ta lastnost nam bo poma- gala dokazati naslednjo lemo.

Lema 2.24. Naj bo A^′ ∈Γ(n). Potem je A^′ permutacijsko podobna matriki oblike

⎡

⎣

U B D

0 P C 0 0 V

⎤

⎦,

kjer sta U, V kvadratni, strogo zgornje trikotni matriki in P permutacijska matrika.

Matriki U in V se ne pojavita nujno. ƒe se matrika U ne pojavi, potem je matrika A^′ permutacijsko podobna matriki

[︃P C 0 V

]︃

.

Podobno, £e matrikaV ne pojavi, potem je matrikaA^′ permutacijsko podobna matriki [︃U B

0 P ]︃

.

V primeru, ko se ne pojavi nobena od matrik U in V, je matrika A^′ permutacijsko podobna matriki P.

Dokaz. Dokazujemo z indukcijo na velikost matrike, torej na n. Za n= 1 lema 2.24 velja trivialno.

Recimo, da lema 2.24 velja za matrike iz Γ(n−1). Lo£imo na dva primera.

(1)MatrikaA^′ je nerazcepna. Po trditvi 2.22 jeA^′ permutacijsko podobna matriki Cn, ki je permutacijska matrika. Torej lema velja.

(2) Matrika A^′ je razcepna. Potem je po trditvi 2.19 matrika A^′ permutacijsko podobna njeni Frobeniusovi normalni obliki. Torej matriki oblike

G=

⎡

⎢

⎢

⎣

A^′₁ A^′₁₂ · · · A^′_1s 0 A^′₂ · · · A^′_2s ... ... ... ...

0 0 · · · A^′_s

⎤

⎥

⎥

⎦ ,

kjer jes≥2inA^′_i ∈M_ni{0,1}je nerazcepna za vsaki= 1, . . . , s. Ker je A^′ ∈Γ(n), je tudi G∈Γ(n). Vemo pa ²e, da je tudi A^′_i ∈Γ(n_i) za vsak i= 1, . . . , s, ker

G^k =

⎡

⎢

⎢

⎣

(A^′₁)^k ⋄ · · · ⋄ 0 (A^′₂)^k · · · ⋄ ... ... ... ...

0 0 · · · (A^′_s)^k

⎤

⎥

⎥

⎦

in G∈Γ(n). Denirajmo

Ω ={t|A^′_t ̸= 0,1≤t≤s}

={t|n_t≥2,1≤t ≤s} ∪ {t|n_t = 1, A^′_t= 1,1≤t ≤s}.

Za i ∈ Ω ozna£imo z W_i cikel ali zanko v grafu D(G), ki ustreza grafu D(A^′_i). Najprej pokaºimo, da ima matrika G naslednje ²tiri lastnosti:

(a)Za vsaki= 1, . . . , s, £e je A^′_i matrika velikostin_i×n_i, kjern_i ≥2, potem jeA^′_i permutacijsko podobna matriki C_ni. To sledi iz trditve 2.22, ker je A^′_i nerazcepna.

(b) Naj boA^′_i nerazcepna diagonalni blok matrikeG. ƒe je A^′_i ni£elna matrika, je velikosti 1×1. To dokaºemo tako, da predpostavimo, da je nerazcepna matrika A^′_i velikosti ni×ni, kjer ni ≥ 2. Po lastnosti (a) je potem A^′_i permutacijsko podobna matriki C_ni. Matrika C_ni pa ima prin_i ≥2neni£elne elemente. Torej A^′_i ni ni£elna matrika. To pa pomeni, da so edine ni£elne nerazcepne matrike v Gvelikosti1×1. (c) Za vsaka razli£na i, j ∈ Ω, ne obstaja sprehod, ki bi povezoval W_i in W_j v D(G). Za taka i, j velja, da je A^′_ij = 0. To dokaºemo tako, da predpostavimo da obstaja sprehod W_pq dolºinek od pdo q, kjer je p vozli²£e vW_i inq vozli²£e v W_j. Po deniciji W_i, je dolºina cikla ali zankeW_i enaka n_i in dolºina W_j enaka n_j. Naj bo d= lcm(n_i, n_j)najmanj²i skupni ve£kratnik n_i inn_j. Potem imamo dva razli£na sprehoda od vozli²£a p do vozli²£a q, ki sta dolºine d+k v D(G):

W :p−→ⁿⁱ

Wi

p−→ⁿⁱ

Wi

p→. . .→p−→ⁿⁱ

Wi

p−−→^k

Wpq

q

W^′ :p−−→^k

Wpq

q −→^nj

Wj

q −→^nj

Wj

q →. . .→q −→^nj

Wj

q, kjer je _n^d_i ciklov ali zank p−→ⁿⁱ

Wi

pv W in _n^d_j ciklov ali zankq −→^nj

Wj

qv W^′. Dobili smo protislovje s tem, da je D(A^′)∈Θ(n)in posledi£no D(G)∈Θ(n).

(d) ƒe je A^′_i = 0, potem je ali A^′_ij = 0 za vsak j ∈ Ω aliA^′_ji = 0 za vsak j ∈Ω. To dokaºemo na naslednji na£in. Recimo, da je A^′_i = 0z n_i = 1, matriki A^′_ij in A^′_ki pa sta neni£elni za j, k ∈ Ω. Ozna£imo z G(u, v) element matrike G v u-ti vrstici in v-tem stolpcu. Recimo, da A^′_i leºi v m-ti vrstici in posledi£no v m-tem stolpcu

matrike G:

G=

⎡

⎢

⎢

⎢

⎢

⎢

⎣

1 · · · m · · · n 1 ∗ · · · A^′_ki · · · ∗ ... 0 ... ... ... ... ... ∗ m 0 · · · A^′_i · · · A^′_ij · · · ∗ ... 0 ... ... ... ... ... ∗ n 0 · · · 0 · · · ∗

⎤

⎥

⎥

⎥

⎥

⎥

⎦

Ker smo predpostavili, da sta matriki A^′_ij in A^′_ki neni£elni, lahko sklepamo, da obstaja p in q, da je G(m, p) =G(q, m) = 1. Potem sta cikla Wk in Wj povezana s sprehodom q→m→p, kar je v protislovju s tem, kar smo dokazali v (c).

Poglejmo si sedaj, kak²ne oblike je matrika G. Lo£imo dva primera.

(i)MatrikaGje nesingularna. Veljadet(G)̸= 0. Ker je G blo£no zgornje trikotna, je det(G) = det(A^′₁) · . . .· det(A^′_s). Sledi, da je det(A^′_i) razli£na od 0 za vsak i = 1, . . . , s. Torej so matrike A^′_i nesingularne. Iz lastnosti (a) matrike G lahko sklepamo, da so A^′_i permutacijsko podobneC_ni, torej so permutacijske matrike. Iz lastnosti (c) matrike G pa lahko sklepamo, da so vsi nediagonalni bloki ni£elne matrike. Iz tega sledi, da je G permutacijska matrika. To ustreza lemi 2.24 v primeru, ko ni blokov U inV.

(ii) Matrika G je singularna. Pokaºimo, da ima G ali vrstico samih ni£el ali pa ima stolpec samih ni£el. Pa recimo, da G nima stolpca samih ni£el, ki mu kraj²e re£emo ni£elni stolpec. Ker je G singularna matrika, ima det(G) = 0, torej ima vsaj en diagonalni blok A^′_i, ki je matrika samih ni£el. Po lastnosti (b) matrike G, je blok A^′_i velikosti 1×1. Naj bo A^′_i

1 prvi ni£elni blok med bloki A^′₁, A^′₂, . . . , A^′_s. Indeks i₁ ne more biti enak 1, ker bi potem imeli ni£elni stolpec. Zato i₁ ≥ 2 in 1, . . . , i₁ −1 ∈ Ω. Ker stolpec, v katerem je A^′_i

1, ni ni£elen stolpec, obstaja nek 1≤ t₀ ≤i₁−1, da velja A^′_t

0,i1 ̸= 0. Ker to velja, potem je po lastnosti (d) matrike G matrika A^′_i1j = 0 za vsak j ∈ Ω. ƒe vrstica i1 ni ni£elna, potem obstaja nek i₂ > i₁, da je A^′_i

1,i2 ̸= 0. Sledi da i₂ ∈/ Ω oziroma A^′_i

2 = 0, ker £e A^′_i

2 ̸= 0, potem bi obstajal sprehod od nekega vozli²£a iz A^′_t0 do nekega vozli²£a A^′_i2 v D(G), kar pa je v protislovju z lasnotstjo (c). Ker je A^′_i2 = 0, potem zaradi istih razlogov kot prej lahko sklepamo, da A^′_i2j = 0 za vsak j ∈ Ω. ƒe vrstica i2 ni ni£elna, potem obstaja nek i₃ > i₂, da A^′_i2,i3 ̸= 0 in A^′_i3 = 0. Ta postopek ponavljamo in enkrat dobimo vrstico samih ni£el, ker je matrika kon£ne velikosti. Po istem postopku lahko pokaºemo, da £e singularna matrika G nima vrstice samih ni£el, potem ima stolpec samih ni£el. ƒe imaGvrstico samih ni£el, potem staGinA^′ permutacijsko podobni matriki oblike

[︃Y ∗ 0 0 ]︃

,

kjer je matrika Y velikosti (n−1)×(n−1). Ker je A^′ ∈ Γ(n), je Y ∈ Γ(n−1). Uporabimo indukcijsko predpostavko na Y in dobimo obliko matrike iz leme 2.24.

ƒe pa ima Gstolpec samih ni£el, potem sta GinA^′ permutacijsko podobni matriki oblike

[︃0 ∗ 0 Z ]︃

,

kjer je matrika Z velikosti (n −1)×(n−1). Ker je A^′ ∈ Γ(n), je Z ∈ Γ(n−1). Uporabimo indukcijsko predpostavko na Z in dobimo obliko matrike iz leme 2.24.

S tem smo zaklju£ili dokaz. □

Lema 2.24 nam pove, kak²ne oblike so matrike A^′ ∈Γ(n), ki pa niso nujno idem- potentne. Oglejmo si, kak²ne oblike je binarna idempotentna matrika.

Izrek 2.25. Matrika A^′ ∈M_n{0,1} je idempotentna natanko tedaj, ko jeA^′ permu- tacijsko podobna matriki oblike

(3) A^′′ =

⎡

⎣

0_r B BC 0 I_s C 0 0 0_t

⎤

⎦, kjer sta r in t ve£ja ali enaka 0 ter s ve£ji od 0.

Dokaz. Naj bo A^′ permutacijsko podobna matriki A^′′ iz (3). Potem je

(A^′′)² =

⎡

⎣

0_r B BC 0 I_s C 0 0 0_t

⎤

⎦

2

=

⎡

⎣

0_r BI_s BC 0 I_s² I_sC 0 0 0_t

⎤

⎦=

⎡

⎣

0_r B BC 0 I_s C 0 0 0_t

⎤

⎦=A^′′.

Torej A^′′ je idempotentna matrika. Ker je A^′ permutacijsko podobna A^′′, velja A^′ = P^TA^′′P. Iz enakosti (A^′)² = P^TA^′′P P^TA^′′P = P^T(A^′′)²P = P^TA^′′P = A^′ sledi, da je A^′ idempotentna.

Naj bo sedaj A^′ ∈ M_n{0,1} idempotentna matrika. O£itno je, da je A^′ ∈ Γ(n). Po lemi 2.24 je A^′ permutacijsko podobna matriki

A^′′₂ =

⎡

⎣

U B^′ D 0 P C^′

0 0 V

⎤

⎦,

kjer sta U, V kvadratni, strogo zgornje trikotni matriki inP permutacijska matrika.

Ker je A^′ idempotentna, je idempotentna tudi A^′′₂. Velja, da je (A^′′₂)² =A^′′₂. Torej (4) A^′′₂ = (A^′′₂)² =

⎡

⎣

U B^′ D 0 P C^′

0 0 V

⎤

⎦

2

=

⎡

⎣

U² U B^′+B^′P U D+B^′C^′+DV 0 P² P C^′+C^′V

0 0 V²

⎤

⎦. MatrikiU inV sta strogo zgornje trikotni, zato sta po lemi 2.6 nilpotentni matriki.

Naj bo k ∈ N tak, da je U^k = 0. Ker velja enakost (4) velja tudi U² = U. Po lemi 2.12 je Uⁿ = U za vsak n ∈ N, torej tudi za n = k. Torej velja enakost U = U^k = 0. Po podobnih sklepih je tudi V = 0. Iz enakosti (4) dobimo D = U D+B^′C^′+DV. Ker staU inV ni£elni matriki, je matrika Denaka matrikiB^′C^′. Matrika P je permutacijska matrika, zato je P^T njen inverz. Po enakosti 4 velja P =P². To pomnoºimo z matrikoP^T in dobimoP =I. Zato je edina idempotentna permutacijska matrika identi£na matrika. Sledi, da je A^′ permutacijsko podobna

matriki iz (3). □

3. ’tevilo moºnih neni£elnih elementov v idempotentnih ni£elno-neni£elnih matrikah

V tem razdelku nas bo zanimalo, koliko ni£el oziroma koliko neni£elnih elementov ima lahko idempotentna ni£elno-neni£elna matrika ob podanem rangu matrike.

Na splo²no ranga ni£elno-neni£elne matrike ne moremo dolo£iti, ker ne vemo to£- nih vrednosti neni£elnih elementov. Pokaºimo to na primeru.

Primer 3.1. Naj bo polje F =Z5. Oglejmo si ni£elno-neni£elno matriko

A=

⎡

⎢

⎢

⎣

0 ∗ 0 ∗ 0 ∗ 0 ∗ 0 0 ∗ ∗ 0 0 0 0

⎤

⎥

⎥

⎦ .

Po izreku 2.14 je A idempotentna ni£elno-neni£elna matrika, ker je matrika

A^′ =

⎡

⎢

⎢

⎣

0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0

⎤

⎥

⎥

⎦

idempotentna. Vse matrike iz Z_Z5(A) nimajo istih rangov. Na primer za matriki

B₁ =

⎡

⎢

⎢

⎣

0 2 0 2 0 3 0 3 0 0 4 1 0 0 0 0

⎤

⎥

⎥

⎦ in B₂ =

⎡

⎢

⎢

⎣

0 2 0 1 0 4 0 3 0 0 1 3 0 0 0 0

⎤

⎥

⎥

⎦

iz mnoºice Z_Z5(A) velja, da je rang matrike B₁ enak2, rang matrike B₂ pa enak 3.

Torej rang(B₂)̸= rang(B₁). ♢

Ni£elno-neni£elnim matrikam zato v splo²nem ne moremo dolo£iti ranga, lahko pa jim deniramo minimalni rang.

Denicija 3.2. Naj bo A ni£elno-neni£elna matrika. Minimalni rang matrike A nad poljem F je deniran kot

mr_F(A) = min{rang(B)|B ∈Z_F(A)}.

Cilj tega razdelka je re²iti naslednji problem.

Problem 3. Dolo£imo ²tevilo moºnih neni£elnih elementov v idempotentni ni£elno- neni£elni matriki s podanim minimalnim rangom.

Naj bo matrika A^′ ∈ M_n{0,1} idempotentna z rangom s. Po izreku 2.25 je A^′ permutacijsko podobna matriki

A^′′ =

⎡

⎣

0_r B BC 0 Is C 0 0 0t

⎤

⎦.

Naj bo A ∈ Ωn(F) matrika, ki jo dobimo iz A^′ tako, da zamenjamo vse enice z

∗. Potem je matrika A idempotentna z minimalnim rangom s, ker ima drugi blok stolpcev vedno s linearno neodvisnih stolpcev. Zato je problem 3 ekvivalentem dolo£anju moºnih ²tevil enic v idempotentni matriki A^′ ∈ M_n{0,1} ob podanem rangu. Za ta namen se posluºimo izreka iz [1, Theorem 2], ki pove kak²ne vrednosti ima funkcija

γ(n) = max{f(A^′)|A^′ ∈Γ(n)},

kjer jef(A^′)²tevilo enic vn×n matrikiA^′. Funkcijaγ(n)predstavlja zgornjo mejo

²tevila enic matrike A^′ ∈Γ(n). ƒe isto funkcijo pogledamo iz vidika teorije grafov, paγ(n)predstavlja zgornjo mejo povezav v grafuD(A^′)zn vozli²£i, ker vsaka enica v matriki A^′ predstavlja eno povezavo v grafuD(A^′).

Lema 3.3 ([1, Theorem 2]). Naj bo n ∈N. Potem je

γ(n) =

{︄_(n+1)2

4 , £e je n liho ²tevilo,

n(n+2)

4 , £e je n sodo ²tevilo.

Naj bo A^′ ∈ Γ(n). Potem je f(A^′) ≤ γ(n) in f(A^′) = γ(n) natanko tedaj, ko je A^′ permutacijsko podobna matriki

⎡

⎣

U E J_r,t 0 P J_s,t

0 0 0

⎤

⎦

ali njeni transponiranki, kjer

• J_r,t ozna£uje r×t matriko samih enic,

• P je s×s permutacijska matrika in se vedno pojavi,

• U je r×r strogo zgornje trikotna matrika, ki se ne pojavi nujno,

• v vsaki vrstici matrike [U, E] se pojavi natanko ena 1. Pri tem je

t= {︄_n−1

2 , £e je n liho ²tevilo,

n

2 −1 ali ⁿ₂, £e je n sodo ²tevilo.

ƒe jen sodo ²tevilo, potemt lahko zasede dve razli£ni vrednosti. To se zgodi, ker obstajata matriki z razli£nim rangom, ki imata natanko γ(n) enic.

Primer 3.4. Naj bo matrika A^′ iz mnoºiceΓ(4). Naj zaA^′ veljaf(A^′) =γ(4) = 6. Po lemi 3.3 je za t= ⁿ₂ = 2 matrikaA^′ permutacijsko podobna matriki

A^′₁ =

⎡

⎢

⎢

⎣

1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0

⎤

⎥

⎥

⎦

in ima rang enak 2, za t = ⁿ₂ −1 pa jeA^′ permutacijsko podobna matriki

A^′₂ =

⎡

⎢

⎢

⎣

1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0

⎤

⎥

⎥

⎦ ,

ki ima rang enak 3. ♢

Funkcija f je odvisna od ranga matrike. Kak²na je ta odvisnost, nam bo pokazal naslednji izrek.

Izrek 3.5. Naj bo A^′ ∈Γ(n) idempotentna matrika z rangom s. (1) ƒe je s= 0, potem je f(A^′) = 0.

(2) ƒe je 1 ≤ s ≤ ⌊ⁿ₂⌋+ 1, potem je s ≤ f(A^′) ≤ γ(n). Pri tem je f(A^′) = s natanko tedaj, ko je A^′ diagonalna matrika in f(A^′) =γ(n) natanko tedaj, ko je A^′ permutacijsko podobna matriki

⎡

⎣

0r E Jr,t

0 Is Js,t

0 0 0_t

⎤

⎦

ali njeni transponiranki, kjer je v vsaki vrstici matrike E natanko ena enica in je t=

{︄_n−1

2 , £e je n liho ²tevilo,

n

2 −1 ali ⁿ₂, £e je n sodo ²tevilo.

(3) ƒe je s > ⌊ⁿ₂⌋+ 1, potem je s ≤ f(A^′) ≤s(n−s+ 1). Pri tem je f(A^′) = s natanko tedaj, ko je A^′ diagonalna in f(A^′) = s(n−s+ 1) natanko tedaj, ko je A^′ permutacijsko podobna matriki

A^′₁ =

[︃I_s Js,n−s

0 0n−s

]︃

ali njeni transponiranki.

Dokaz. Ker je A^′ ∈Γ(n) idempotentna matrika, je permutacijsko podobna matriki

A^′′ =

⎡

⎣

0r B BC 0 I_s C 0 0 0_t

⎤

⎦.

’tevilo enic f(A^′) je enaka ²tevilu enic f(A^′′), ker sta si A^′ in A^′′ permutacijsko podobni.

(1) ƒe je s= 0, potem jeA^′ matrika samih ni£el. Sledi, da jef(A^′) = 0.

(2) Naj bo 1≤s≤ ⌊ⁿ₂⌋+ 1. Zaradi bloka I_s v matriki A^′′ velja, da je f(A^′)≥s. Torej bo f(A^′) =s natanko tedaj, ko bo

A^′′ =

⎡

⎣

0r 0 0 0 I_s 0 0 0 0_t

⎤

⎦. Ker je A^′ ∈Γ(n) in

t = {︄_n−1

2 , £e jen liho ²tevilo,

n

2 −1 ali ⁿ₂, £e jen sodo ²tevilo,

lahko uporabimo lemo 3.3 in zato velja s ≤ f(A^′) ≤ γ(n). Po isti lemi velja tudi, da je f(A^′) = γ(n) natanko tedaj, ko je A^′ permutacijsko podobna matriki

A^′₃ =

⎡

⎣

U E J_r,t 0 P Js,t

0 0 0

⎤

⎦

ali njeni transponiranki, kjer so t in matrike U, E, Jr,t, Js,t, P kot navedeno v lemi 3.3. Ker jeA^′ idempotentna, je A^′ = (A^′)². Prav tako to velja za matrikoA^′₃, ker je (A^′₃)² =P^TA^′P P^TA^′P =P^TA^′P =A^′₃. Torej

⎡

⎣

U E J_r,t 0 P J_s,t

0 0 0

⎤

⎦=A^′₃ = (A^′₃)² =

⎡

⎣

U E J_r,t 0 P J_s,t

0 0 0

⎤

⎦

2

=

⎡

⎣

U² U E+EP U J_r,t+EJ_s,t

0 P² P J_s,t

0 0 0

⎤

⎦. Matrika U je strogo zgornje trikotna matrika. Po lemi 2.6 je potem U nilpotentna matrika. Naj bo k ∈ N tak, da je U^k = 0. Ker je A^′₃ = (A^′₃)² velja tudi U² = U. Po lemi 2.12 je Uⁿ = U za vsak n ∈ N, torej tudi za n = k. Torej velja enakost