HIMPUNAN RENTANGAN DAN BEBAS LINIER
HIMPUNAN RENTANGAN
Definisi (Kombinasi Linier) Misalkan V suatu ruang vektor atas field F. w vektor di V, dan v1 ,
, vn juga vektor-
vektor di V. Vektor w dikatakan sebagai kombinasi linier dari vektor-vektor v1 ,
, vn
jika w dapat dinyatakan dalam bentuk w r1v1
rn vn
, rn F .
di mana r1 ,
Suatu himpunan vektor merentang ruang vektor jika setiap vektor dalam ruang vektor tersebut dapat dinyatakan sebagai kombinasi linier dari beberapa vektor dalam himpunan tersebut.
Definisi (Himpunan Rentangan) Subruang yang direntang oleh S tak kosong, S suatu himpunan bagian dari V, adalah himpunan dari seluruh kombinasi linier vektor- vektor dalam S:
S span(S ) {r1v1 Jika S {v1 ,
span v1 ,
rnvn | ri F , vi S}
, vn } merupakan himpunan hingga, kita gunakan notasi v1 ,
, vn atau
, vn . Suatu himpunan vektor S dalam V dikatakan merentang V, atau
membangun V, jika V span(S ) . S disebut himpunan rentangan.
Sembarang superset dari himpunan rentangan juga merupakan himpunan rentangan. Semua ruang vektor memiliki himpunan rentangan, karena V merentang dirinya sendiri.
1
BEBAS LINIER
Definisi (bebas linier) Misalkan V suatu ruang vektor. Himpunan vektor-vektor S dalam V dikatakan bebas linier jika untuk sebarang vektor yang berbeda s1 , a1s1
an sn 0
, sn dalam S,
ai 0
untuk semua i.
Dengan kata lain S bebas secara linier jika untuk vektor 0, jika seluruh koefisien dari kombinasi liniernya dari S adalah 0.
Definisi lain dari bebas linier adalah S dikatakan bebas linier jika vektor 0 dapat dinyatakan secara unik sebagai kombinasi linier vektor-vektor dari S. Pernyataan 0 s1 1s1 memiliki dua interpretasi 1. 0 as1 bs1 Di mana a = 1 dan b = -1, akan tetapi pernyataan 1 tidak melibatkan dua vektor yang berbeda sehingga tidak dapat dikatakan sebagai bebas linier. 2. 0 s1 t1 Di mana t1 s1 s1 (asumsi s1 0 ), Jika S bebas linier, maka S tidak mengandung s1 dan s1 .
Definisi (essentially unique) Misalkan S himpunan vektor dalam ruang vektor V. Vektor tak nol v V dikatakan sebagai kombinasi linier yang unik esensial dari vektor-vektor dalam S jika terdapat satu dan hanya satu cara untuk menyatakan v sebagai kombinasi linier v a1s1
an sn
di mana si merupakan vektor yang berbeda dalam S, dan koefisien ai 0 . Secara eksplisit, v 0 merupakan kombinasi linier yang unik esensial dari vektorvektor dalam S jika v S dan jika ketika v a1s1
an sn dan v b1t1
bmtm
di mana si vektor-vektor yang berbeda dalam S, begitu pun ti vektor-vektor yang berbeda dalam S, dan semua koefisien ai dan bi tak nol, maka m = n dan setelah
2
dilakukan pengindeksan ulang bi ti , kita dapatkan ai bi dan si ti untuk semua i 1, 2,..., n
Teorema 1.6 Misalkan S {0} merupakan himpunan vektor tak nol dalam V. Maka pernyataan berikut ekivalen: 1. S bebas secara linier 2. setiap vektor tak nol v span(S ) dinyatakan secara unik esensial kombinasi linier dari vektor-vektor di S. 3. tidak ada vektor dalam S yang merupakan kombinasi linier dari vektor-vekor lainnya dalam S. Bukti: (1 2)
Misalkan S bebas linier dan 0 v a1s1
an sn b1t1
bmtm
di mana si vektor-vektor yang berbeda dalam S, begitu pun ti vektor-vektor yang berbeda dalam S, dan koefisien ai dan bi tak nol. Dengan mengurangi dan mengelompokkan s dan t yang sama, 0 (ai1 bi1 )si1
(aik bik )sik aik 1 sik 1
ain sin bik 1 tik 1
bim tim
Karena S bebas linier mengakibatkan n = m = k, aiu biu , dan siu tiu untuk semua i 1, 2,..., k . (2 3)
Andaikan ada s S yang dapat ditulis sebagai s a1s1
an sn
Di mana si S dan berbeda dengan s, ambil vektor tak nol v span(S ) 0 v k1s1
kn sn ks
0 v k1s1
kn sn k (a1s1
v (k1 ka1 )s1
an sn )
(kn kan )sn
Sehingga v tidak unik esensial. Kontradiksi dengan yang diketahui. (3 1)
3
Misalkan S tidak bebas linier dan a1s1
an sn 0
di mana si vektor-vektor yang berbeda dalam S dan ai tak nol, maka untuk n > 1, s1
1 (a2 s2 a1
an sn )
Berarti terdapat vektor dalam S yang merupakan kombinasi linier dari vektor lainnya dalam S. Kontradiksi dengan yang diketahui bahwa tidak terdapat vektor dalam S yang dapat dinyatakan sebagai kombinasi linier vektor lainnya dalam S.
Teorema 1.7 Misalkan S himpunan vektor dalam V. Maka pernyataan berikut ekivalen: 1. S bebas secara linier dan merentang V 2. setiap vektor tak nol v V adalah kombinasi linier yang unik esensial dari vektor-vektor di S 3. S himpunan terentang minimal, S merentang V tapi sebarang proper subset dari S tidak merentang V 4. S himpunan bebas linier maksimal, S bebas linier tapi sebarang proper superset dari S tidak bebas linier. Suatu himpunan vektor di V yang memenuhi sembarang kondisi di atas disebut basis dari V. Bukti: (1 2)
telah dibuktikan pada teorema sebelumnya. (1 3)
S himpunan terentang. Andaikan ada S ' S juga merentang V, maka sebarang vektor dalam S – S’ merupakan kombinasi linier dari vektor-vektor dalam S’. Sehingga terdapat vektor dalam S yang merupakan kombinasi linier dari vektor- vektor di S’, S ' S . Dengan kata lain terdapat vektor dalam S yang merupakan kombinasi linier dari vektor-vektor lain di S. Maka S tidak bebas linier .Hal tersebut kontradiksi dengan yang diketahui bahwa S bebas linier. (3 1)
4
Andaikan S tidak bebas linier, terdapat vektor s S merupakan kombinasi linier dari vektor lainnya dalam S, sehingga S – {s} merupakan subhimpunan rentangan sejati dari S. Kontradiksi dengan yang diketahui. (1 4)
Andaikan S bukan maksimal, maka akan ada vektor v V S sehingga S {v} bebas linier. Akan tetapi karena v bukan dalam rentangan S, maka kontradiksi dengan yang diketahui bahwa S himpunan rentangan. (4 1)
Jika S tidak merentang V, maka terdapat v V S bukan kombinasi linier dari vekotr – vektor dalam S. Sehingga S {v} merupakan superset bebas linier sejati dari S, yang merupakan kontradiksi.
Teorema 1.8 Himpunan hingga S {v1 ,
, vn } di V merupakan basis untuk V jika dan hanya jika
V v1
vn
Bukti: Misalkan Si {v | v rvi , r F} Si vi ()
S {v1 ,
, vn } di V merupakan basis untuk V, artinya
S bebas linier dan merentang V. Jika S merentang V maka V span(S ) {r1v1 V {r1v1
rnvn | vi S , ri F}
n
rn vn | vi S , ri F } Si
jika S bebas linier maka r1v1
1)
i 1
rnvn 0 , ri 0 .
Ambil vektor tak nol v Sk karena S bebas linier maka v tidak dapat dinyatakan sebagai kombinasi linier {v1 ,..., vk 1 , vk 1 ,..., vn } . Sehingga vektor tak nol v bukan
5
elemen dari Sk
n
i 1,i k
Si . Sedangkan untuk 0 Sk , 0 0.vk dan 0 dapat dinyatakan
sebagai kombinasi linier dari {v1 ,..., vk 1 , vk 1 ,..., vn } , 0 rv 1 1
rk 1vk 1 rk 1vk 1
sehingga 0
n
i 1,i k
rnvn , rv i i Si
Si . Oleh karena 0 Sk dan 0 Sk
n
i 1,i k
n
i 1,i k
Si ,
Si {0}
Dari 1) dan 2), didapat V S1
2)
Sn v1
vn
()
Diketahui V v1
vn , akan dibuktikan S {v1 ,
, vn } basis untuk V
Akan ditunjukkan: S merentang V dan bebas linier Bukti:
Si {v | v rvi , r F} Si vi V v1
vn , berarti
1. v V ,
v r1v1
rnvn n
di mana Si sehinggga V Si {r1v1 i 1
rn vn | vi S , ri F } .
Pernyataan di atas menyatakan V sebagai kumpulan semua kombinasi linier dari v1 ,
, vn , dengan kata lain {v1 ,..., vn } merentang V.
2. Sk
n
i 1,i k
Misalkan v1 ,
Si {0} , vn tidak bebas linier maka berdasarkan teorema 1.6, terdapat vektor
vk yang dapat dinyatakan sebagai kombinasi linier vektor – vektor {v1 ,..., vk 1 , vk 1 ,..., vn } , sehingga sebarang v Sk dapat dinyatakan sebagai kombinasi
linier dari {v1 ,..., vk 1 , vk 1 ,..., vn } , v r1v1
rk 1vk 1 rk 1vk 1
rn vn
n
i 1,i k
Si .
6
jadi didapat v Sk
Sk
n
i 1,i k
Jika Sk
n
i 1,i k
Si {0} . Kontradiksi dengan yang diketahui
Si {0} n
i 1,i k
Karena v1 ,
Si {0} maka v1 ,
, vn bebas linier.
, vn merentang V dan bebas linier, maka v1 ,
, vn merupakan basis
untuk V.
Contoh 1.6 Vektor standar ke-i dalan Fn adalah vektor
ei yang bernilai 0 pada semua posisi
koordinat kecuali koordinat ke-i, dmana pada posisi ke-i bernilai 1. e1 (1,0,...,0), e2 (0,1,...,0), ..., en (0,0,...1)
Himpunan e1 ,..., en merupakan basis standar untuk Fn .
Definisi (himpunan te rurut parsial) Himpunan terurut parsial (poset) adalah pasangan ( P, ) di mana P himpunan tak kosong dan suatu relasi biner yang disebut terurut parsial, dengan memenuhi sifat berikut: 1. (refleksif), untuk semua a P aa
2. (antismetri) untuk semua a, b, c P
a b dan b a
a b
ac
3. (transitif) untuk semua a, b, c P
a b dan b c Definisi
Poset yang mana tiap pasang elemennya dapat dibandingkan disebut himpunan terurut total atau himpunan terurut linier. Sembarang himpunan bagian terurut total dari poset P disebut chain dalam P.
7
Zorn’s Lemma Jika P adalah suatu himpunan terurut parsial (poset) yang mana tiap chain memiliki batas atas, maka P memiliki suatu elemen maksimal.
Teorema 1.9 Misalkan V ruang vector tak nol. Misalkan I himpunan bebas linier dalam V dan misalkan S himpunan merentang dalam V mengandung I. Maka terdapat basis B untuk V di mana I B S . 1. sembarang ruang vektor, kecuali ruang vektor nol {0}, memiliki basis. 2. sembarang himpunan bebas linier dalam V dimuat dalam basis. 3. sembarang himpunan rentangan dalam V mengandung basis.
Bukti: Pandang A sebagai semua subset bebas linier dari V yang mengandung I dan dimuat oleh S. Himpunan tersebut tidak kosong, karena I A . Misalkan C {I k | k K}
merupakan chain di A, maka gabungan U
I k juga bebas linier dan memenuhi kK
I U S . Setiap chain di A memiliki batas atas dan menurut Zorn’s lemma, A pasti
memiliki elemen maksimal B, yang bebas linier. Misalkan B basis untuk ruang vektor S V . Jika untuk sembarang s S bukan kombinasi linier dari vektor-vektor di B, maka B {s} S bebas linier. Kontradiksi dengan yang diketahui, B elemen maksimal.
Sehingga S B dan juga V S B .
8
