29 Rank-Bir Matris Tamamlama, Sirkülantlar

Bipartite graph ile tamamlanabilirlik, cyclic shift P ve evrişimin matris hâli

Bölüm bilgisi

Bu ders iki yeni konu açar: rank-1 matris tamamlama (bir matrisin bazı girdileri verilince kalanı rank-1 olacak şekilde doldurulabilir mi?) ve sirkülant matrisler (her satır bir öncekinin döngüsel kaydırılmışı — sinyal-işleme/CNN bloğunun temeli). Strang’in Ders 30 videosu (≈50 dk) ve OCW Lecture 30 temel alınmıştır. Okuma süresi ≈34 dk. Ders 28-29 kayıt edilmemiş lab oturumlarıdır; sinyal-işleme bloğu bu derste başlıyor. Önkoşul Ders 1 ($uv^{\top}$ dış-çarpım), Ders 16 (matris tamamlama) ve Ders 4 (özvektör).

29.1 Bu Derste Ne Var?

İki konu. (A) Rank-1 matris tamamlama: bir matrisin bazı girdileri verilince, kalanı rank-1 olacak şekilde doldurulabilir mi? (B) Sirkülant matrisler: her satır bir öncekinin döngüsel kaydırılmışı; sinyal-işleme/CNN bloğunun temeli.

Beş sonuç:

Rank-1 tamamlama: $A = uv^{\top}$, $a_{ij} = u_i v_j$; $m+n-1$ serbest parametre. Rank-1 ⇔ tüm 2×2 alt-determinantlar = 0.
Bipartite graph: satırlar + sütunlar düğüm, verilen girdiler kenar; tamamlanabilir ⇔ döngü (cycle) yok.
Sirkülant C: ilk kolon tümünü belirler (cyclic shift P); $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$, $P^n = I$.
Sirkülant çarpımı = cyclic convolution: sirkülantlar grup oluşturur (CD de sirkülant).
Özvektörler = P’nin özvektörleri = birim kökleri ($1, -1, i, -i$ for $n=4$) → Fourier matrisi (Ders 31).

“…every circulant matrix is a polynomial in P…” — Strang, 32:45

flowchart TD
    C["Ders 30: iki konu"]

    C --> A["Dal A - rank-1 tamamlama:<br/>A = uv^T, m+n-1 girdi, 2x2 det = 0"]
    C --> B["Dal B - sirkulant:<br/>ilk kolon belirler, C = polinom(P), P^n = I"]

    A --> A1["bipartite graph dongusuz<br/>&lt;=&gt; tamamlanabilir"]
    B --> B1["carpim = cyclic convolution (grup)"]
    B --> B2["ozvektorler = birim kokleri -&gt; Fourier"]

    K1["D1 uv^T dis-carpim"]
    K2["D16 Netflix tamamlama"]
    K3["D31 Fourier matrisi (sonraki)"]
    K4["CNN/evrisim (D32, fast.ai L15)"]

    N["D28-29 kayitsiz lab —<br/>sinyal-isleme blogu burada basliyor"]

    K1 --> A
    K2 --> A
    B2 --> K3
    B1 --> K4

    classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff;
    classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff;
    classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330;
    classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff;

    class C merkez;
    class A,B,A1,B1,B2 dal;
    class K1,K2,K3,K4 vec;
    class N teal;

Şekil 29.1: Ders 30 kavram haritasi: iki konu tek koprude bulusuyor. Dal A rank-1 tamamlama (A = uv^T, m+n-1 girdi yeter, her 2x2 alt-determinant sifir; bipartite graph dongusuz ise tamamlanabilir). Dal B sirkulant matrisler (ilk kolon tum matrisi belirler, C = polinom(P) ve P^n = I; carpim = cyclic convolution = grup islemi; ozvektorler birim kokleri -> Fourier). Koprular: D1 uv^T dis-carpim, D16 Netflix tamamlama, D31 Fourier matrisi (sonraki), CNN/evrisim (D32, fast.ai L15). D28-29 kayitsiz lab atlanir; sinyal-isleme blogu bu derste basliyor.

Şekil 29.1 dersin iskeletini gösterir: merkezdeki “iki konu” fikrinden iki dala ayrılır — Dal A (rank-1 tamamlama: $A = uv^{\top}$, $m+n-1$ girdi yeter, her 2×2 alt-determinant sıfır; bipartite graph döngüsüz ise tamamlanabilir) ve Dal B (sirkülant: ilk kolon tüm matrisi belirler, $C = $ polinom$(P)$, $P^n = I$; çarpım = cyclic convolution grup işlemi; özvektörler birim kökleri → Fourier); köprü düğümleri D1 $uv^{\top}$ dış-çarpım, D16 Netflix tamamlama, D31 Fourier matrisi (sonraki) ve CNN/evrişim (D32, fast.ai L15) iki dalı önceki ve sonraki derslere bağlar; ayrı bir teal düğüm D28-29 kayıtsız lab oturumlarını işaretler — sinyal-işleme bloğu burada başlar.

Builder Notu — İki Konu Tek Köprü

Bu ders iki bağımsız gibi görünen konuyu tek bir derste topluyor; ama ikisi de yapı → cebir köprüsünün örneği. ML köprüsü: rank-1 tamamlama, Ders 16’nın Netflix matris tamamlamasının kombinatoryal/yapısal versiyonudur (hangi gözlem desenleri tamamlamaya izin verir?); sirkülant matrisler ise evrişimin (CNN, Ders 32) ve FFT’nin (Ders 31) lineer-cebir temelidir. Geriye köprü: Ders 1 ($uv^{\top}$ dış-çarpım, kolon×satır), Ders 16 (matris tamamlama/nuclear norm), Ders 4 (özvektör). İleriye: Ders 31 (Fourier — sonraki).

Tek cümle: Rank-1 matris tamamlama bir bipartite graph’ın döngüsüz olmasıyla mümkündür; sirkülant matrisler ise tek bir döngüsel kaydırma P’nin polinomudur, çarpımları döngüsel evrişimdir ve özvektörleri birim kökleridir (Fourier).

29.2 Rank-1 Matris Tamamlama Problemi

İlk konu, Prof. Rao’nun lab’ından doğan bir soru:

“…can you complete it to a rank 1 matrix?” — Strang, 1:22

Bir matrisin bazı girdileri verilmiş (geri kalanı boş). Boşları, sonuç rank-1 olacak şekilde doldurabilir misin? Rank-1 matris dış-çarpımdır (Ders 1):

\[A = uv^{\top}, \qquad a_{ij} = u_i\,v_j\]

Kaç girdi serbestçe verilebilir? $m$ tane $u$, $n$ tane $v$ var; ama $u$’yu yeniden ölçekleyip $u_1 = 1$ yapabiliriz (bir serbestlik tekrarlı). Yani $m + n - 1$ serbest parametre. $m = n = 3$ için 5 girdi. Bu girdiler sıfırdan farklı olmalı (sıfır verilen bir konum, o satır/sütunu sıfıra zorlardı). Bu beş girdinin nasıl zincirleme dokuz girdiye açıldığını Şekil 29.2 bir sonraki bölümde sayılarla gösterir.

Builder Notu — Dış-Çarpımın Geri Dönüşü

“Rank-1 = $uv^{\top}$, $m+n-1$ serbestlik” Ders 1’in dış-çarpım görüşünün geri dönüşü. ML köprüsü: bu, Ders 16’nın Netflix matris tamamlamasının (eksik kullanıcı-film matrisini düşük-rank doldur) kombinatoryal/yapısal versiyonu — hangi gözlem desenleri tamamlamaya izin verir? Öneri sistemlerinde “hangi girdiler yeterli?” sorusu.

29.3 2×2 Determinant Kuralı

Rank-1 olmanın testi: her 2×2 alt-matris tekildir (determinantı sıfır). Çünkü rank-1’de tüm kolonlar bir kolonun katı, tüm satırlar bir satırın katı:

\[\det\begin{bmatrix} a_{ij} & a_{ik} \\ a_{lj} & a_{lk} \end{bmatrix} = 0 \quad (\text{her } 2\times2)\]

Bu, boş girdileri doldurmanın anahtarı: bir 2×2’nin üç girdisi biliniyorsa, dördüncüsü determinantı sıfır yapacak tek değerdir ($a_{ik} = a_{ij}\cdot a_{lk}/a_{lj}$). Bilinen girdilerden başlayıp 2×2 kuralıyla komşuları zincirleme doldurursun.

Kod

from matplotlib.patches import Rectangle

u, v, A = make_rank1(3, 3, seed=30)
pos = tree_pattern(3, 3)
A_hat = rank1_complete({p: A[p] for p in pos}, 3, 3)

fig, axes = plt.subplots(1, 3, figsize=(11.5, 3.8))

# --- Sol: verilen 5 girdi (agac deseni) ---
ax = axes[0]
M = np.full((3, 3), np.nan)
for (i, j) in pos:
    M[i, j] = A[i, j]
Mm = np.ma.masked_invalid(M)
cmap = NAVY_CMAP
cmap.set_bad(color="#ffffff")
vmin = float(np.nanmin(M)); vmax = float(np.nanmax(M))
text_thresh = vmin + 0.62 * (vmax - vmin)
ax.imshow(Mm, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal")
for i in range(3):
    for j in range(3):
        if not np.isnan(M[i, j]):
            v_ = M[i, j]
            ax.text(j, i, "{:.2f}".format(v_), ha="center", va="center",
                    color="#ffffff" if v_ >= text_thresh else COL_TEXT,
                    fontsize=11, fontweight="bold")
        else:
            ax.text(j, i, "?", ha="center", va="center", color="#999999",
                    fontsize=15, fontweight="bold")
ax.set_xticks(range(3)); ax.set_yticks(range(3))
ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0)
for sp in ax.spines.values(): sp.set_color(COL_STEEL_300)
ax.set_title("verilen: m+n-1 = 5 girdi (agac)", color=COL_TEXT, fontsize=12, fontweight="bold")

# --- Orta: 2x2 kurali semasi ---
ax = axes[1]
B = np.array([[A_hat[0, 0], A_hat[0, 1]],
              [A_hat[1, 0], A_hat[1, 1]]])
vmin2 = float(np.min(B)); vmax2 = float(np.max(B))
if abs(vmax2 - vmin2) < 1e-12: vmax2 = vmin2 + 1.0
tt2 = vmin2 + 0.62 * (vmax2 - vmin2)
ax.imshow(B, cmap=NAVY_CMAP, vmin=vmin2, vmax=vmax2, aspect="equal")
for i in range(2):
    for j in range(2):
        v_ = B[i, j]
        ax.text(j, i, "{:.2f}".format(v_), ha="center", va="center",
                color="#ffffff" if v_ >= tt2 else COL_TEXT,
                fontsize=12, fontweight="bold")
ax.add_patch(Rectangle((0.5, 0.5), 1.0, 1.0, fill=False, edgecolor=COL_VEC3, lw=3))
ax.text(0.5, -0.85, "a22 = a12*a21/a11", ha="center", va="center",
        color=COL_TEXT, fontsize=11, fontweight="bold")
ax.text(0.5, 1.85, "det = 0 -> TEK deger", ha="center", va="center",
        color=COL_VEC3, fontsize=11, fontweight="bold")
ax.set_xlim(-0.5, 1.5); ax.set_ylim(2.1, -1.1)
ax.axis("off")

# --- Sag: tamamlanmis A_hat tam heatmap ---
heatmap(axes[2], A_hat, title="tamamlandi: 9/9, maxdiff 2.2e-16",
        cmap=NAVY_CMAP, annotate=True, fmt="{:.2f}", fontsize=11)

fig.suptitle("Bes girdiden dokuz girdi: 2x2 det=0 kurali zincirleme her boslugu TEK degerle "
             "doldurur (maxdiff 2.2e-16, tum 2x2 det = 0)",
             fontsize=12.5, fontweight="bold", color=COL_TEXT, y=1.06)
plt.tight_layout()
plt.show()

Şekil 29.2: Beş girdiden dokuz girdi: 2×2 det=0 kuralı zincirleme her boşluğu TEK değerle doldurur — solda verilen m+n−1 = 5 girdilik ağaç deseni, ortada a₂₂ = a₁₂·a₂₁/a₁₁ kuralı (det=0 → tek değer), sağda 9/9 geri kazanılmış A_hat (maxdiff 2.2e-16, tüm 2×2 det ≈ 0).

Şekil 29.2 solda verilen 5 girdilik ağaç desenini (satır-0 + kolon-0; boş hücreler “?”), ortada $a_{22} = a_{12}\cdot a_{21}/a_{11}$ kuralını (det=0 → tek değer, turuncu vurgu), sağda tamamlanmış $A_{\text{hat}}$’ı gösterir: beş girdiden başlayıp 2×2 det=0 kuralını zincirleyerek dokuz girdinin tamamı geri kazanılır, maxdiff $2.2\times10^{-16}$ ve $A_{\text{hat}}$’ın tüm 2×2 determinantları $\approx 0$. 4×5’te de 8 girdiden 20 girdi aynı kesinlikle gelir.

Builder Notu — Rank’ı Küçük Pencerelerden Oku

“Rank-1 ⟺ tüm 2×2 det = 0” rank’ın yerel karakterizasyonu: rankı global SVD’den değil, küçük determinantlardan oku. ML köprüsü: bu kural, matris tamamlamanın neden bazı desenlerde benzersiz (her boşluk tek değer) bazılarında imkânsız (çelişen kısıtlar) olduğunu açıklar — düşük-rank tamamlamanın belirlenebilirlik (identifiability) koşulu.

29.4 Bipartite Graph ve Tamamlanabilirlik

Hangi konumlar tamamlamaya izin verir? Bir kombinatorikçinin görüşü: problemi bir bipartite grapha (iki-parçalı çizge) çevir.

“…this is called a bipartite graph.” — Strang, 12:02

Satırları bir parça ($m$ düğüm), sütunları diğer parça ($n$ düğüm) yap. Verilen her $(i,j)$ girdisi, satır-$i$ ile sütun-$j$ arasına bir kenar koyar. $m+n-1$ girdi → $m+n-1$ kenar. Kural: matris tamamlanabilir ⟺ bu graf döngüsüzdür (cycle yok, yani bir orman/ağaç). Bir döngü, tüm girdileri verilmiş bir 2×2 (veya daha büyük) demektir — orada determinantı sıfır zorlayamazsın, çelişki çıkar.

\[\text{tamamlanabilir} \iff \text{bipartite graph dongusuz (forest)}\]

Döngüsüz graf, 2×2 kuralını çelişkisiz zincirlemene izin verir; her boş girdi tek değerle belirlenir.

Kod

fig, axes = plt.subplots(1, 2, figsize=(9.5, 4.2))

# Sol: ağaç (forest) deseni — 5 kenar mavi
draw_bipartite(axes[0], tree_pattern(3, 3), 3, 3, title="döngüsüz (forest) -> tamamlanabilir")

# Sağ: döngü deseni — 4 kenar turuncu
cyc = [(0, 0), (0, 1), (1, 0), (1, 1)]
draw_bipartite(axes[1], cyc, 3, 3, edge_colors=[COL_VEC3]*4, title="döngü r1-c1-r2-c2 -> çelişki riski")
axes[1].text(0.5, -0.02, "değerler 2,6,1,5: det = 2*5-6*1 = 4 != 0 -> İMKANSIZ (motor: None)",
             ha="center", va="top", color=COL_TEXT, fontsize=8.5)

fig.suptitle("Tamamlanabilirlik saf graf sorusu: kenarlar döngü kapatıyorsa determinantı sıfır zorlayamazsın — motor çelişkiyi yakalar",
             color=COL_TEXT, fontsize=10.5, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()

Şekil 29.3: Tamamlanabilirlik saf graf sorusu: kenarlar döngü kapatıyorsa determinantı sıfır zorlayamazsın — motor çelişkiyi yakalar

Şekil 29.3 solda döngüsüz (forest) ağaç desenini gösterir — beş kenar bir orman oluşturur, tamamlanabilir; sağda $(1,1),(1,2),(2,1),(2,2)$ kenarları bir döngü kapatır (r1-c1-r2-c2). Bu döngüde değerler $2,6,1,5$ verilince det $= 2\cdot5 - 6\cdot1 = 4 \neq 0$ olduğundan rank-1 tamamlama imkânsızdır (motor None döner); determinantı sıfır zorlayamazsın.

Builder Notu — Cebir Graf Olunca

“Tamamlanabilir ⟺ bipartite graph döngüsüz” zarif bir cebir-graf köprüsü: matris yapısı (rank-1 doldurulabilirlik) saf grafik teorisine (döngü var mı?) indirgenir. ML köprüsü: graf-tabanlı düşünme öneri sistemlerinde merkezî — kullanıcı-ürün bipartite grafı, eksik kenarları (tahmin) tamamlamak; döngü/bağlılık yapısı hangi tahminlerin güvenilir olduğunu belirler. Cebir ↔︎ graf çevirisi Phase 2’nin tekrarlayan teması.

29.5 Sirkülant Matris ve Cyclic Shift P

İkinci konu: sirkülant (dolaşımlı) matris. Her kolon, bir öncekinin döngüsel kaydırılmışıdır — yani ilk kolonu verirsen tüm matris belli. Anahtar yapı taşı döngüsel kaydırma matrisi P:

“…the key matrix in this is really a cyclic shift matrix.” — Strang, 28:21

\[P = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}\]

P bir vektörü bir aşağı kaydırır, en alttaki döngüsel olarak tepeye döner. P bir permütasyon matrisidir. $P^2$ iki kaydırma, $P^3$ üç kaydırma. P’nin kuvvetlerinin bir sonraki bölümde $P^4 = I$ ile başa döndüğünü Şekil 29.4 gösterir.

Builder Notu — Bir Kolon Bütün Matris

“İlk kolon → tüm matris, cyclic shift P” sirkülantın sıkıştırılmış temsili: $n\times n$ matris yerine $n$ sayı (ilk kolon). ML köprüsü: bu, evrişimin (convolution) matris hâlidir — bir filtreyi tüm konumlara kaydırarak uygula; CNN’in ağırlık paylaşımı (weight sharing) tam bu döngüsel/kaydırmalı yapı. Toeplitz matrisi (Ders 32) sirkülantın döngüsüz akrabasıdır.

29.6 C = Polinom(P), Pⁿ = I

Her sirkülant matris, P’nin bir polinomudur (köşegenlere $c_0, c_1, c_2, c_3$ koymak = P kuvvetlerinin kombinasyonu):

“…every circulant matrix is a polynomial in P…” — Strang, 32:45

\[C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3\]

Kritik özellik: $n\times n$’de $P^n = I$ ($n$ kaydırma başa döner). Yani P’nin kuvvetleri $\{I, P, \dots, P^{n-1}\}$ ile sınırlı — derecesi $n$’i aşan terimler döngüsel olarak geri sarar. Bu sayede sirkülantlar bir grup oluşturur: iki sirkülantın çarpımı (iki polinomun çarpımı) yine bir sirkülanttır ($P^n=I$ ile dereceyi $n$’in altında tutarak).

Kod

P = cyclic_P(4)
mats = [P, P @ P, np.linalg.matrix_power(P, 3), np.linalg.matrix_power(P, 4)]
titles = ["P (1 kaydırma)", "P^2", "P^3", "P^4 = I (başa döndü)"]

fig, axes = plt.subplots(1, 4, figsize=(11.5, 3.2))
for ax, M, t in zip(axes, mats, titles):
    heatmap(ax, M, title=t, fmt="{:.0f}")
fig.suptitle(
    "Döngüsel kaydırma P permütasyondur; P^4 = I — kuvvetler {I, P, P^2, P^3} ile sınırlı; "
    "sirkülant C = c0 I + c1 P + c2 P^2 + c3 P^3",
    color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.93])
plt.show()

Şekil 29.4: Döngüsel kaydırma P permütasyondur; P^4 = I — kuvvetler {I, P, P^2, P^3} ile sınırlı; sirkülant C = c0 I + c1 P + c2 P^2 + c3 P^3 olarak bu dört kuvvetin doğrusal birleşimidir.

Şekil 29.4 $P, P^2, P^3, P^4$ kuvvetlerini sırayla gösterir: her kaydırma 1’leri bir köşegen ilerletir ve $P^4 = I$ başa döner. Demek ki P’nin kuvvetleri $\{I, P, P^2, P^3\}$ ile sınırlıdır; sirkülant $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$ tam bu dört kuvvetin doğrusal birleşimidir. Motor tanığı: P döngüsel kaydırma, $P^4 = I$, $P^3 \neq I$ ve $P\cdot(1,2,3,4) = (4,1,2,3)$ (bir aşağı, sarmalı).

Builder Notu — Matris Dünyasından Polinom Dünyasına

“Sirkülant = polinom($P$), $P^n=I$” cebirsel kalbi: matris dünyasını polinom dünyasına çevirir. ML köprüsü: bu, evrişimin neden polinom çarpımı (ve Fourier’de basit çarpma) olduğunu açıklar; $P^n=I$ döngüselliği, ayrık Fourier dönüşümünün (DFT, Ders 31) periyodikliğinin kaynağı. Polinom ↔︎ matris ↔︎ sinyal üç dil aynı şey.

29.7 Cyclic Convolution

Sirkülant çarpımı, polinom çarpımıdır — yani evrişim (convolution). Örnek: $(3,1,2) \circledast (4,6,1)$, gizli polinomlar $(3 + x + 2x^2)(4 + 6x + x^2)$:

\[(3, 1, 2) * (4, 6, 1) = (12, 22, 17, 13, 2)\]

(İlkokul çarpması: terim terim çarp-topla.) Sirkülantlarda $P^n = I$ olduğundan döngüsel (cyclic) evrişim: taşan terimler başa sarar.

“…I’m just doing cyclic convolution actually.” — Strang, 36:48

\[(3, 1, 2) \circledast (4, 6, 1) = (12+13,\ 22+2,\ 17) = (25, 24, 17)\]

$n=3$’te $P^3=I$, böylece 5-uzunluklu sonuç 3’e sarılır. Hoş bir sağlama: rakam-toplamları çarpımı korunur — $(3+1+2)(4+6+1) = 6\cdot11 = 66 = 25+24+17$. Matris çarpımı = döngüsel evrişim = polinom çarpımı (mod $P^n-1$).

Kod

c = np.array([3., 1, 2]); d = np.array([4., 6, 1])
lin = linear_conv(c, d)      # (12,22,17,13,2)
cyc = cyclic_conv(c, d)      # (25,24,17)
C = circulant(c)             # ilk kolon (3,1,2)

fig, axes = plt.subplots(1, 3, figsize=(12, 4))

# Sol: C = circulant(3,1,2) heatmap
heatmap(axes[0], np.array(C, dtype=float), title="C: ilk kolon (3,1,2) tümünü belirler", fmt="{:.0f}")

# Orta: doğrusal evrişim 5 bar — ilk üç navy, son iki turuncu + sarmalama okları
ax = axes[1]
bar_colors = [COL_PRIMARY, COL_PRIMARY, COL_PRIMARY, COL_VEC3, COL_VEC3]
xs = np.arange(len(lin))
ax.bar(xs, lin, color=bar_colors, edgecolor=COL_TEXT, linewidth=0.8, zorder=3)
for x, v in zip(xs, lin):
    ax.text(x, v + 0.5, f"{v:.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold")
ax.annotate("13 -> +12 ye sarar", xy=(3, 13.3), xytext=(0.55, 24.0),
            arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.8), color=COL_VEC3, fontsize=8.5, fontweight="bold")
ax.annotate("2 -> +22 ye sarar", xy=(4, 2.3), xytext=(1.6, 13.5),
            arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.8), color=COL_VEC3, fontsize=8.5, fontweight="bold")
ax.set_title("doğrusal: (12,22,17,13,2)", color=COL_TEXT, fontsize=12, fontweight="bold")
ax.set_ylim(0, 26)
ax.set_xticks(xs)
apply_style(ax)

# Sağ: döngüsel sonuç 3 bar navy (25,24,17) + sağlama metni
ax = axes[2]
xs2 = np.arange(len(cyc))
ax.bar(xs2, cyc, color=COL_PRIMARY, edgecolor=COL_TEXT, linewidth=0.8, zorder=3)
for x, v in zip(xs2, cyc):
    ax.text(x, v + 0.5, f"{v:.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold")
ax.text(0.5, 0.92, "sağlama: 6*11 = 66 = 25+24+17", transform=ax.transAxes,
        ha="center", va="top", color=COL_TEXT, fontsize=9.5, fontweight="bold",
        bbox=dict(boxstyle="round,pad=0.3", facecolor=COL_BG, edgecolor=COL_STEEL_300))
ax.set_title("döngüsel (P^3 = I): (25,24,17)", color=COL_TEXT, fontsize=12, fontweight="bold")
ax.set_ylim(0, 30)
ax.set_xticks(xs2)
apply_style(ax)

fig.suptitle("Sirkülant çarpımı = polinom çarpımı = cyclic convolution: taşan terimler P^n = I ile başa sarar",
             color=COL_TEXT, fontsize=12.5, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()

Şekil 29.5: Sirkülant çarpımı = polinom çarpımı = cyclic convolution: taşan terimler P^n = I ile başa sarar — (3,1,2) çark (4,6,1) = (25,24,17). Doğrusal evrişim (12,22,17,13,2); taşan son iki terim 13 ve 2 başa sarınca döngüsel sonuç (25,24,17). Sağlama: 6*11 = 66 = 25+24+17.

Şekil 29.5 solda $C = \text{circulant}(3,1,2)$ heatmap’ini (ilk kolon tümünü belirler), ortada doğrusal evrişimi $(12,22,17,13,2)$ — taşan son iki terim $13$ ve $2$ turuncu, sarmalama okları $13 \to +12$ ve $2 \to +22$ — ve sağda döngüsel sonucu $(25,24,17)$ gösterir. Sağlama: $6\cdot11 = 66 = 25+24+17$. Taşan terimler $P^n = I$ ile başa sarar; matris çarpımı = polinom çarpımı = cyclic convolution.

Builder Notu — Üç Dilin Aynı Çarpımı

“Sirkülant çarpımı = cyclic convolution = polinom çarpımı” üç dilin birliği. ML köprüsü: CNN’lerin (Ders 32) konvolüsyon katmanı tam budur; fast.ai L15’in im2col/conv2d’si konvolüsyonu matris çarpımına çevirir. FFT (Ders 31) konvolüsyonu $O(n \log n)$’de yapar — sinyal işleme ve büyük-çekirdek CNN’lerin hızı buradan.

29.8 Özvektörler = Birim Kökleri (Fourier)

Sirkülant C’nin özvektörleri ne? C = P’nin polinomu olduğundan, C’nin özvektörleri P’nin özvektörleriyle aynı (P’nin özvektörü, $P^2$’nin ve $P^3$’ün de özvektörü):

“…the eigenvectors of C are the same as the eigenvectors of P.” — Strang, 45:01

Demek ki tek soru: P’nin özvektörleri/özdeğerleri ne? P döngüsel kaydırma; özdeğerleri birim kökleri (roots of unity). $n=4$ için $(1,1,1,1) \to \lambda=1$; $(1,-1,1,-1) \to \lambda=-1$; ve karmaşık $(1, i, -1, -i) \to \lambda=i, \lambda=-i$:

“…the eigenvectors are the four roots of 1.” — Strang, 48:42

\[\lambda(P) = 1, -1, i, -i = e^{2\pi i k/n}, \quad k = 0, 1, 2, 3\]

Özvektörler birim köklerinden kurulur — bunlar Fourier matrisinin kolonlarıdır (Ders 31). Yani TÜM sirkülantlar aynı özvektörleri (Fourier) paylaşır.

Kod

fig, axes = plt.subplots(1, 3, figsize=(12, 4))

# Sol: birim cember + 4 kok
ax = axes[0]
theta = np.linspace(0, 2*np.pi, 200)
ax.plot(np.cos(theta), np.sin(theta), color=COL_STEEL_300, lw=1.0, zorder=1)
roots = [(1, 0), (0, 1), (-1, 0), (0, -1)]
labels = ["1", "i", "-1", "-i"]
for (x, y), lab in zip(roots, labels):
    ax.scatter([x], [y], s=120, color=COL_PRIMARY, zorder=3)
    ax.annotate(lab, (x, y), textcoords="offset points", xytext=(10, 10),
                color=COL_TEXT, fontsize=12, fontweight="bold")
ax.axhline(0, color=COL_STEEL_300, lw=0.8); ax.axvline(0, color=COL_STEEL_300, lw=0.8)
ax.set_title(r"$\lambda(P) = $ birim kökleri $e^{2\pi i k/4}$", color=COL_TEXT, fontsize=12, fontweight="bold")
ax.set_xlim(-1.4, 1.4); ax.set_ylim(-1.4, 1.4)
apply_style(ax); ax.set_aspect("equal")

# Orta: F^-1 C F kosegen heatmap
ax = axes[1]
F = fourier_matrix(4)
rng = np.random.default_rng(30)
c4 = rng.uniform(-2, 2, 4)
C4 = circulant(c4)
off, diag = diag_offmax(F, C4)
heatmap(ax, np.abs(np.linalg.solve(F, C4 @ F)), title=r"$F^{-1} C F$ köşegen (off-diag 5.8e-16)", fmt="{:.2f}")

# Sag: iki farkli sirkulant kosegen bar
ax = axes[2]
d1 = np.abs(np.fft.fft(c4))
d2 = np.abs(np.fft.fft(c4*2 + 1))
x = np.arange(4)
ax.bar(x - 0.18, d1, width=0.36, color=COL_PRIMARY, label="C1")
ax.bar(x + 0.18, d2, width=0.36, color=COL_VEC3, label="C2")
ax.annotate("köşegen = FFT(c) — Ders 31", xy=(0.46, 0.93), xycoords="axes fraction",
            ha="center", color=COL_TEXT, fontsize=9, fontweight="bold")
ax.set_title(r"farklı $C$'ler AYNI $F$'de köşegenleşir", color=COL_TEXT, fontsize=12, fontweight="bold")
ax.set_xticks(x); ax.legend(loc="upper right")
apply_style(ax)

fig.suptitle("TÜM sirkülantların özvektörleri aynı: birim köklerinden kurulan Fourier kolonları — evrişim çarpmaya döner (Ders 31)",
             color=COL_TEXT, fontsize=12, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 29.6: TÜM sirkülantların özvektörleri aynı: birim köklerinden kurulan Fourier kolonları — evrişim çarpmaya döner (Ders 31). Sol: $\lambda(P)$ birim çemberdeki dördüncü birim kökleri. Orta: $F^{-1}CF$ köşegen (off-diag 5.8e-16). Sağ: iki farklı sirkülant AYNI $F$’de köşegenleşir, köşegen = FFT(c).

Şekil 29.6 solda $\lambda(P)$’yi birim çemberdeki dört birim kökü ($1, i, -1, -i$) olarak, ortada $F^{-1}CF$’in köşegen olduğunu (köşegen-dışı $5.8\times10^{-16}$), sağda iki FARKLI sirkülantın AYNI $F$’de köşegenleştiğini (köşegen $= \text{FFT}(c)$, Ders 31) gösterir. Motor tanığı: $F^{-1}CF$ köşegen-dışı $5.8\times10^{-16}$, köşegen $= \text{np.fft.fft}(c)$ birebir, ve farklı sirkülant da aynı $F$’de köşegenleşir (ortak özvektör tabanı).

Bu dersin son sorusu — sirkülant özvektörünü P ile çarpınca hangi özdeğer çıkar — Egzersiz 4’te somutlaşır; Şekil 29.7 motor cevabını verir.

Kod

x = np.array([1, 1j, -1, -1j])
Px = cyclic_P(4) @ x

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9, 3.8))

# Sol: karmaşık düzlemde 4 bileşen — x (navy ok) ve Px (turuncu kesik ok)
theta = np.linspace(0, 2*np.pi, 200)
ax1.plot(np.cos(theta), np.sin(theta), color=COL_STEEL_300, linewidth=1.0, alpha=0.7)
for i in range(4):
    ax1.annotate("", xy=(x[i].real, x[i].imag), xytext=(0, 0),
                 arrowprops=dict(arrowstyle="-|>", color=COL_PRIMARY, lw=2.0))
    ax1.annotate("", xy=(Px[i].real, Px[i].imag), xytext=(0, 0),
                 arrowprops=dict(arrowstyle="-|>", color=COL_VEC3, lw=1.6, linestyle="--"))
labels = ["x1", "x2", "x3", "x4"]
for i in range(4):
    ax1.text(x[i].real*1.18, x[i].imag*1.18, labels[i], color=COL_PRIMARY,
             fontsize=11, ha="center", va="center", fontweight="bold")
ax1.set_xlim(-1.5, 1.5); ax1.set_ylim(-1.5, 1.5)
ax1.set_xlabel("gerçek"); ax1.set_ylabel("sanal")
ax1.set_title("P her bileşeni -90 derece döndürür")
apply_style(ax1); ax1.set_aspect("equal")

# Sağ: iki hata barı — λ = -i tam tutar (0), λ = +i tutmaz (2)
err_neg = np.max(np.abs(Px - (-1j)*x))
err_pos = np.max(np.abs(Px - (1j)*x))
bars = ax2.bar([0, 1], [err_neg, err_pos], color=[COL_PRIMARY, COL_VEC3], width=0.6)
ax2.set_xticks([0, 1])
ax2.set_xticklabels(["|Px - (-i)x| = 0", "|Px - (+i)x| != 0"])
ax2.set_ylabel("maksimum hata")
ax2.set_title("lambda = -i (i DEĞİL) [motor notu]")
for b, v in zip(bars, [err_neg, err_pos]):
    ax2.text(b.get_x()+b.get_width()/2, v+0.05, f"{v:.1f}",
             ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold")
ax2.set_ylim(0, 2.4)
apply_style(ax2)

fig.suptitle("Egzersiz 4 motor cevabı: P(1,i,-1,-i) = -i (1,i,-1,-i) — aşağı-kaydırmada lambda = -i; eşlenik kolon (1,-i,-1,i) +i alır",
             color=COL_TEXT, fontsize=10)
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 29.7: Egzersiz 4 motor cevabı: P(1,i,-1,-i) = -i (1,i,-1,-i) — aşağı-kaydırmada lambda = -i; eşlenik kolon (1,-i,-1,i) +i alır. Sol panelde x bileşenleri (navy) ve Px bileşenleri (turuncu kesik) her biri -90° dönmüş; sağ panelde |Px - (-i)x| = 0 (tam tutar) ile |Px - (+i)x| = 2 (tutmaz) karşılaştırması.

Şekil 29.7 solda $x = (1, i, -1, -i)$ bileşenlerini (navy) ve $Px$ bileşenlerini (turuncu kesik) gösterir — P her bileşeni $-90°$ döndürür; sağda iki hata barı $|Px - (-i)x| = 0$ (tam tutar) ile $|Px - (+i)x| \neq 0$ ($= 2$, tutmaz) karşılaştırır.

motor notu — Egz4 özdeğeri ve §7’deki iki kök

Notion §7’deki “$(1, i, -1, -i) \to \lambda=i, \lambda=-i$” cümlesi iki karmaşık özdeğeri birden anar (P’nin spektrumunda hem $+i$ hem $-i$ vardır) ve Egzersiz 4 “(i ile mi?)” sorusunu açık bırakır. Bu aşağı-kaydırma P (yani $(Px)_i = x_{(i-1)\bmod n}$) için motor cevabı kesindir: $x = (1, i, -1, -i)$ özvektörünün özdeğeri $\lambda = -i$’dir ($i$ DEĞİL) — $P\cdot x = -i\cdot x$. Eşlenik kolon $(1, -i, -1, i)$ ise $\lambda = +i$ alır. İki kök birden P’nin spektrumunda yaşar; ama bu spesifik kolon-özvektör eşleşmesi $(1, i, -1, -i) \mapsto -i$ şeklindedir.

Builder Notu — Bütün Sirkülantların Ortak Tabanı

“Tüm sirkülantların özvektörleri = Fourier” sinyal işlemenin temel teoremi: Fourier tabanında her sirkülant köşegenleşir, evrişim çarpmaya döner. ML köprüsü: bu, FFT’nin (Ders 31) ve frekans-uzayı filtrelemenin temeli; konvolüsyon teoremi (zaman uzayında evrişim = frekans uzayında çarpma) doğrudan buradan. Graf sinyal işleme (NYU spektral GCN, Ders 19/35) bu fikri graf Laplacian özvektörlerine genelleştirir. Köşegen değerleri tam $\text{FFT}(c)$ olduğundan, Ders 31’in $F^{-1}CF = \text{diag}(\text{FFT}(c))$ köprüsü buradan açılır.

29.9 Bu Dersin Özeti

Rank-1 tamamlama: $A = uv^{\top}$, $a_{ij} = u_i v_j$; $m+n-1$ serbest parametre. Rank-1 ⟺ tüm 2×2 det = 0.
Bipartite graph: satır+sütun düğüm, girdi=kenar; tamamlanabilir ⟺ döngüsüz (forest).
Sirkülant C: ilk kolon tümünü belirler; cyclic shift P; $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$; $P^n = I$.
Grup + cyclic convolution: iki sirkülantın çarpımı sirkülant; çarpım = döngüsel evrişim = polinom çarpımı (mod $P^n-1$).
Özvektörler: C’nin özvektörleri = P’nin özvektörleri = birim kökleri ($1, -1, i, -i$ for $n=4$) = Fourier matrisi.
Tüm sirkülantlar aynı özvektörleri (Fourier) paylaşır → evrişim çarpmaya döner (Ders 31).

Tek Bir Cümle

Rank-1 matris tamamlama bir bipartite graph’ın döngüsüz olmasıyla mümkündür (her boş girdi 2×2 det=0 ile tek değer alır); sirkülant matrisler ise tek bir döngüsel kaydırma P’nin polinomudur, çarpımları döngüsel evrişimdir ve özvektörleri birim kökleridir — yani hepsi Fourier matrisinde köşegenleşir.

29.10 Kontrol Soruları

Soru 1 — Kaç girdi serbest ve rank-1’in testi

Soru: Rank-1 matris tamamlamada kaç girdi serbestçe verilebilir ve rank-1’in testi nedir?

Cevap: $m+n-1$ girdi ($A = uv^{\top}$’de $m$ tane $u$ + $n$ tane $v$, ama $u_1=1$ normalize edilince bir serbestlik düşer). Verilen girdiler sıfırdan farklı olmalı. Rank-1 testi: tüm 2×2 alt-determinantlar sıfır olmalı (tüm kolonlar bir kolonun katı). Bir 2×2’nin üç girdisi biliniyorsa, dördüncüsü det=0 yapacak tek değerdir.

Soru 2 — Bipartite graph tamamlanabilirliği nasıl belirler

Soru: Bipartite graph rank-1 tamamlanabilirliği nasıl belirler?

Cevap: Satırlar bir parça, sütunlar diğer parça düğümleri; verilen her $(i,j)$ girdisi satır-$i$ ↔︎ sütun-$j$ kenarı. Matris tamamlanabilir ⟺ bu graf döngüsüzdür (forest/ağaç). Döngü, tüm girdileri verilmiş bir alt-yapı demektir; orada determinantı sıfır zorlayamazsın (çelişki). Döngüsüz graf, 2×2 kuralını çelişkisiz zincirlemene izin verir.

Soru 3 — Sirkülant neden P’nin polinomu ve neden grup

Soru: Sirkülant matris neden P’nin polinomudur ve neden grup oluşturur?

Cevap: Sirkülant C, köşegenlerinde $c_0, c_1, c_2, c_3$ taşır; bunlar tam olarak P kuvvetlerinin katsayılarıdır: $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$ (P = döngüsel kaydırma). $P^n = I$ ($n$ kaydırma başa döner) olduğundan, iki sirkülantın çarpımı (iki polinomun çarpımı) yine $n$’den küçük dereceli bir polinom = sirkülanttır. Bu yüzden grup: çarpım kapalı, I birim eleman.

Soru 4 — Sirkülantın özvektörleri ve neden önemli

Soru: Sirkülant matrisin özvektörleri nedir ve bu neden önemli?

Cevap: C = P’nin polinomu olduğundan C’nin özvektörleri = P’nin özvektörleri. P döngüsel kaydırmanın özdeğerleri birim kökleridir ($e^{2\pi i k/n}$; $n=4$ için $1, -1, i, -i$), özvektörleri Fourier matrisinin kolonları. Önemli çünkü TÜM sirkülantlar aynı (Fourier) özvektörleri paylaşır — Fourier tabanında her sirkülant köşegenleşir, dolayısıyla evrişim çarpmaya dönüşür (konvolüsyon teoremi, FFT temeli, Ders 31).

29.11 Egzersizler

2×2 tamamlama. Bir 2×2 matrisin üç girdisi: $a_{11}=2$, $a_{12}=6$, $a_{21}=1$. Rank-1 olması için $a_{22}$ ne olmalı? (det=0 kuralı: $a_{22} = a_{12}\cdot a_{21}/a_{11}$.) (Motor tanığı: $a_{22} = 6\cdot1/2 = 3.0$.)
Bipartite döngü. 3×3 matriste $(1,1),(1,2),(2,1),(2,2)$ girdileri verilmiş. Bunu bipartite graf olarak çiz; bir döngü var mı? Rank-1 tamamlama mümkün mü, neden? (Motor tanığı: bu dört girdi r1-c1-r2-c2 döngüsü kapatır; değerler $2,6,1,5$ ile det $= 2\cdot5 - 6\cdot1 = 4 \neq 0$ → tamamlama imkânsız (motor None). Aynı döngü $2,6,1,3$ (det=0) ile çelişkisiz geçer, ama bu şans, kural değil; bkz. Şekil 29.3.)
Cyclic convolution. $(1, 2) \circledast (3, 4)$ döngüsel evrişimini ($n=2$, $P^2=I$) hesapla. (Önce normal evrişim $(1,2)*(3,4)$, sonra sarmala.) (Motor tanığı: doğrusal $(3, 10, 8)$ → döngüsel $(3+8, 10) = (11, 10)$; sağlama $3\cdot7 = 21 = 11+10$.)
Sirkülant özvektör. 4×4 cyclic shift P için $(1, i, -1, -i)$ vektörünü P ile çarp (bir aşağı kaydır, sarmala). Hangi $\lambda$ ile özvektör? (i ile mi?) ([motor notu]: Bu aşağı-kaydırma P için $P\cdot(1, i, -1, -i) = -i\cdot(1, i, -1, -i)$, yani $\lambda = -i$ — $i$ DEĞİL. Eşlenik kolon $(1, -i, -1, i)$ ise $\lambda = +i$ alır; bkz. Şekil 29.7.)
(Ders 31 habercisi) Bu derste sirkülantların özvektörlerinin birim kökleri olduğunu gördük. Bu özvektörleri kolon kolon bir matrise dizersen ne elde edersin? $n\times n$ bu matrisin adı ne, hangi dönüşümü temsil eder? Bir tahmin yaz — Ders 31 “sirkülant matrislerin özvektörleri: Fourier matrisi”ni işliyor. (Motor tanığı: özvektörleri kolon kolon dizince $F^{-1}CF = \text{diag}(\text{np.fft.fft}(c))$, yani $F$ tüm sirkülantları köşegenleştirir — ortak özvektör tabanı.)

29.12 Sonraki Ders İçin Hazırlık

Ders 31: Sirkülant Matrislerin Özvektörleri — Fourier Matrisi. Bu dersin birim-kök özvektörlerini bir matrise dizince Fourier matrisi (F) çıkar; ayrık Fourier dönüşümü (DFT). Her sirkülant F’de köşegenleşir, evrişim çarpmaya döner (konvolüsyon teoremi), ve FFT bu yapıyı $O(n \log n)$’de hesaplar — sinyal işleme ve CNN’lerin matematiksel temeli.

Hazırlık

Bu dersin Egzersiz 5’inin sorduğu soruyu zihninde tut: sirkülantların birim-kök özvektörlerini kolon kolon bir matrise dizersen hangi matris çıkar? Ders 31, bu Fourier matrisini (F) tanımlar ve her sirkülantın $F^{-1}CF = \text{diag}(\text{FFT}(c))$ ile köşegenleştiğini gösterir — köşegen değerleri tam FFT(c). Bu, evrişimi çarpmaya çeviren konvolüsyon teoreminin, FFT’nin ($O(n \log n)$) ve sinyal-işleme/CNN bloğunun (Ders 32) matematiksel kalbidir.

29.13 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
Rank-1 tamamlama	$A = uv^{\top}$; $m+n-1$ girdi; tüm 2×2 det = 0	1m22
Bipartite graph	satır/sütun düğüm, girdi=kenar; döngüsüz ⟺ tamamlanabilir	12m02
Cyclic shift P	sirkülant: ilk kolon tümünü belirler	28m21
C = polinom(P)	$c_0 I + c_1 P + c_2 P^2 + c_3 P^3$; $P^n = I$	32m45
Cyclic convolution	sirkülant çarpımı = döngüsel evrişim	36m48
Özvektörler = P’nin	C = polinom(P) → aynı özvektörler	45m01
Birim kökleri → Fourier	$\lambda(P) = 1, -1, i, -i = e^{2\pi i k/n}$	48m42

29.14 ML Bağlantıları Özeti

Sirkülant = evrişim = CNN: sirkülant matrisle çarpmak döngüsel evrişim; CNN’in (Ders 32) ağırlık paylaşımı; fast.ai L15 im2col/conv2d aynı yapı.
Özvektörler Fourier → FFT: tüm sirkülantlar Fourier’de köşegenleşir; evrişim çarpmaya döner (konvolüsyon teoremi); FFT $O(n \log n)$ (Ders 31).
Rank-1 tamamlama: Ders 16 Netflix matris tamamlamasının kombinatoryal hali; bipartite graf döngüsü belirlenebilirliği verir.
Cebir ↔︎ graf: rank-1 doldurulabilirlik saf grafik teorisine (döngü var mı?) indirgenir; öneri sistemleri bipartite graf düşünür.
Graf sinyal işleme: sirkülant→Fourier fikri graf Laplacian özvektörlerine genelleşir (spektral GCN, NYU paralel, Ders 19/35).
Geriye köprü: Ders 1 ($uv^{\top}$ dış-çarpım), Ders 16 (matris tamamlama/nuclear norm), Ders 4 (özvektör). Paralel: fast.ai L15 (convolution), NYU H6 (CNN).

Kapanış

“…the eigenvectors of C are the same as the eigenvectors of P.” — Strang, 45:01

Tüm sirkülantlar tek bir özvektör tabanını (Fourier) paylaşır; bu, evrişimi çarpmaya çeviren konvolüsyon teoreminin ve tüm sinyal işlemenin kalbidir — sinyal/CNN bloğunun açılışı.

--- title: "Rank-Bir Matris Tamamlama, Sirkülantlar" subtitle: "Bipartite graph ile tamamlanabilirlik, cyclic shift P ve evrişimin matris hâli" --- ::: {.callout-note title="Bölüm bilgisi"} Bu ders iki yeni konu açar: **rank-1 matris tamamlama** (bir matrisin bazı girdileri verilince kalanı rank-1 olacak şekilde doldurulabilir mi?) ve **sirkülant matrisler** (her satır bir öncekinin döngüsel kaydırılmışı — sinyal-işleme/CNN bloğunun temeli). Strang'in [Ders 30 videosu](https://www.youtube.com/watch?v=p-bXJIa7QVI) (≈50 dk) ve [OCW Lecture 30](https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-30-completing-a-rank-one-matrix-circulants/) temel alınmıştır. Okuma süresi ≈34 dk. **Ders 28-29 kayıt edilmemiş lab oturumlarıdır; sinyal-işleme bloğu bu derste başlıyor.** Önkoşul Ders 1 ($uv^{\top}$ dış-çarpım), Ders 16 (matris tamamlama) ve Ders 4 (özvektör). ::: ```{python} #| echo: false """ _engine30.py — MIT 18.065 Ders 30 (Rank-Bir Matris Tamamlama + Sirkülantlar) motor + viz. İki dünya: (A) kombinatoryal — 2×2 det=0 zinciri + bipartite döngü (union-find); (B) cebirsel — cyclic shift P, C=polinom(P), cyclic convolution, Fourier köşegenleştirme. Setup hücresi = cat. Figür testi `from _engine30 import *`. matplotlib.use("Agg") burada YOK. """ import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import LinearSegmentedColormap from collections import deque, defaultdict COL_PRIMARY = "#1f4e79"; COL_ACCENT = "#2e75b6"; COL_TEXT = "#13243a" COL_BG = "#eaf1f8"; COL_STEEL_300 = "#aac4dd"; COL_SKY_400 = "#6fa8dc" COL_WHITE = "#ffffff" COL_VEC1 = "#1f4e79"; COL_VEC2 = "#2e75b6"; COL_VEC3 = "#e67e22" COL_TEAL = "#17a2b8"; COL_PURPLE = "#6f42c1" NAVY_CMAP = LinearSegmentedColormap.from_list("strang_navy", ["#ffffff", "#cfe0f0", "#6fa8dc", "#2e75b6", "#1f4e79"]) DIVERGE = LinearSegmentedColormap.from_list("div", [COL_VEC3, "#ffffff", COL_PRIMARY]) def apply_style(ax): ax.set_facecolor(COL_WHITE); ax.grid(True, alpha=0.25, color=COL_STEEL_300, linewidth=0.8) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) ax.tick_params(colors=COL_TEXT); ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT) return ax def heatmap(ax, M, title=None, cmap=None, annotate=True, fmt="{:.2g}", vmin=None, vmax=None, fontsize=11, text_thresh=None): M = np.asarray(M, dtype=float) if cmap is None: cmap = NAVY_CMAP if vmin is None: vmin = float(np.min(M)) if vmax is None: vmax = float(np.max(M)) if abs(vmax - vmin) < 1e-12: vmax = vmin + 1.0 ax.imshow(M, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal"); nr, nc = M.shape if text_thresh is None: text_thresh = vmin + 0.62*(vmax-vmin) if annotate and nr*nc <= 36: for i in range(nr): for j in range(nc): v = M[i, j] ax.text(j, i, fmt.format(v), ha="center", va="center", color=COL_WHITE if v >= text_thresh else COL_TEXT, fontsize=fontsize, fontweight="bold") ax.set_xticks(range(nc)); ax.set_yticks(range(nr)); ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) if title: ax.set_title(title, color=COL_TEXT, fontsize=12, fontweight="bold") # ============ (A) RANK-1 MATRİS TAMAMLAMA ============ def make_rank1(m=3, n=3, seed=30): """Gerçek rank-1 hedef matris A = uvᵀ (girdileri sıfırdan uzak tutulur).""" rng = np.random.default_rng(seed) u = rng.uniform(0.5, 2.0, m) * rng.choice([-1, 1], m) v = rng.uniform(0.5, 2.0, n) * rng.choice([-1, 1], n) return u, v, np.outer(u, v) def tree_pattern(m, n): """m+n−1 girdilik AĞAÇ (yıldız) deseni: satır-0'ın tüm girdileri + kolon-0'ın kalan girdileri.""" return [(0, j) for j in range(n)] + [(i, 0) for i in range(1, m)] def has_cycle(positions, m, n): """Bipartite graf (satır i ↔ sütun j kenarları) union-find döngü testi.""" parent = list(range(m + n)) def find(a): while parent[a] != a: parent[a] = parent[parent[a]]; a = parent[a] return a for (i, j) in positions: ra, rb = find(i), find(m + j) if ra == rb: return True parent[ra] = rb return False def rank1_complete(entries, m, n, tol=1e-9): """2×2 det=0 kuralının zincirlemesi = bipartite grafta BFS ile u,v çözümü. entries: dict (i,j) -> a_ij. Forest ise A_hat = uvᵀ döner (ölçek serbestliği dış-çarpımda yok olur); döngü ÇELİŞKİ üretirse None döner.""" adj = defaultdict(list) for (i, j), w in entries.items(): adj[("r", i)].append((("c", j), w)) adj[("c", j)].append((("r", i), w)) val = {} for start in list(adj): if start in val: continue val[start] = 1.0 # bileşen kökü: ölçek seçimi dq = deque([start]) while dq: node = dq.popleft() for nb, w in adj[node]: want = w / val[node] # a_ij = u_i v_j her iki yönde if nb in val: if abs(val[nb] - want) > tol: # döngü kapanışı tutarsız → çelişki return None else: val[nb] = want; dq.append(nb) uu = np.array([val.get(("r", i), 0.0) for i in range(m)]) vv = np.array([val.get(("c", j), 0.0) for j in range(n)]) return np.outer(uu, vv) def all_2x2_maxdet(A): """Rank-1 testi: tüm 2×2 alt-determinantların mutlak maksimumu (rank-1 → 0).""" A = np.asarray(A, dtype=float); m, n = A.shape; worst = 0.0 for i in range(m): for l in range(i + 1, m): for j in range(n): for k in range(j + 1, n): worst = max(worst, abs(A[i, j]*A[l, k] - A[i, k]*A[l, j])) return worst def draw_bipartite(ax, positions, m, n, edge_colors=None, title=None): """Bipartite graf şeması: solda satır düğümleri, sağda sütun düğümleri, kenar=verilen girdi.""" ys_r = np.linspace(0.9, 0.1, m); ys_c = np.linspace(0.9, 0.1, n) for idx, (i, j) in enumerate(positions): col = COL_ACCENT if edge_colors is None else edge_colors[idx] ax.plot([0.15, 0.85], [ys_r[i], ys_c[j]], color=col, lw=2.2, zorder=1) for i in range(m): ax.scatter([0.15], [ys_r[i]], s=620, color=COL_PRIMARY, zorder=2) ax.text(0.15, ys_r[i], f"r{i+1}", ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold", zorder=3) for j in range(n): ax.scatter([0.85], [ys_c[j]], s=620, color=COL_VEC3, zorder=2) ax.text(0.85, ys_c[j], f"c{j+1}", ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold", zorder=3) ax.set_xlim(0, 1); ax.set_ylim(0, 1); ax.axis("off") if title: ax.set_title(title, color=COL_TEXT, fontsize=12, fontweight="bold") # ============ (B) SİRKÜLANT MATRİSLER ============ def cyclic_P(n=4): """Döngüsel kaydırma matrisi: (Px)_i = x_{(i-1) mod n} — bir AŞAĞI kaydır, alttaki tepeye sarar.""" P = np.zeros((n, n)) for i in range(n): P[i, (i - 1) % n] = 1.0 return P def circulant(c): """C = c0·I + c1·P + c2·P² + … (ilk kolonu c olan sirkülant).""" c = np.asarray(c, dtype=complex); n = len(c); P = cyclic_P(n) C = np.zeros((n, n), dtype=complex); Pk = np.eye(n) for k in range(n): C += c[k] * Pk Pk = P @ Pk return C.real if np.allclose(C.imag, 0) else C def linear_conv(a, b): """Normal (doğrusal) evrişim — polinom çarpımı, uzunluk len(a)+len(b)−1.""" return np.convolve(np.asarray(a, float), np.asarray(b, float)) def cyclic_conv(a, b): """Döngüsel evrişim: out[(i+j) mod n] += a_i b_j (taşan terimler başa sarar, Pⁿ=I).""" a = np.asarray(a, float); b = np.asarray(b, float); n = len(a) out = np.zeros(n) for i in range(n): for j in range(n): out[(i + j) % n] += a[i] * b[j] return out def fourier_matrix(n=4): """F[j,k] = ω^{jk}, ω = e^{2πi/n} — kolonları P'nin özvektörleri (birim köklerinden).""" w = np.exp(2j * np.pi / n) j, k = np.meshgrid(np.arange(n), np.arange(n), indexing="ij") return w ** (j * k) def is_circulant(M, tol=1e-10): """Her kolon bir öncekinin döngüsel kaydırılmışı mı? (grup kapalılığı testi).""" M = np.asarray(M); n = M.shape[0] return all(np.allclose(M[:, k], np.roll(M[:, 0], k), atol=tol) for k in range(n)) def diag_offmax(F, C): """F⁻¹CF'in köşegen-dışı mutlak maksimumu (köşegenleşme tanığı) + köşegeni.""" D = np.linalg.solve(F, C @ F) off = D - np.diag(np.diag(D)) return float(np.max(np.abs(off))), np.diag(D) ``` ## Bu Derste Ne Var? {#sec-bu-derste-d30} İki konu. **(A) Rank-1 matris tamamlama:** bir matrisin bazı girdileri verilince, kalanı rank-1 olacak şekilde doldurulabilir mi? **(B) Sirkülant matrisler:** her satır bir öncekinin döngüsel kaydırılmışı; sinyal-işleme/CNN bloğunun temeli. Beş sonuç: 1. **Rank-1 tamamlama:** $A = uv^{\top}$, $a_{ij} = u_i v_j$; $m+n-1$ serbest parametre. Rank-1 ⇔ tüm 2×2 alt-determinantlar = 0. 2. **Bipartite graph:** satırlar + sütunlar düğüm, verilen girdiler kenar; tamamlanabilir ⇔ **döngü (cycle) yok**. 3. **Sirkülant C:** ilk kolon tümünü belirler (cyclic shift P); $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$, $P^n = I$. 4. **Sirkülant çarpımı = cyclic convolution:** sirkülantlar grup oluşturur (CD de sirkülant). 5. **Özvektörler = P'nin özvektörleri = birim kökleri** ($1, -1, i, -i$ for $n=4$) → Fourier matrisi (Ders 31). > *"...every circulant matrix is a polynomial in P..." — Strang, 32:45* ```{mermaid} %%| label: fig-kavram-haritasi-l30 %%| fig-cap: "Ders 30 kavram haritasi: iki konu tek koprude bulusuyor. Dal A rank-1 tamamlama (A = uv^T, m+n-1 girdi yeter, her 2x2 alt-determinant sifir; bipartite graph dongusuz ise tamamlanabilir). Dal B sirkulant matrisler (ilk kolon tum matrisi belirler, C = polinom(P) ve P^n = I; carpim = cyclic convolution = grup islemi; ozvektorler birim kokleri -> Fourier). Koprular: D1 uv^T dis-carpim, D16 Netflix tamamlama, D31 Fourier matrisi (sonraki), CNN/evrisim (D32, fast.ai L15). D28-29 kayitsiz lab atlanir; sinyal-isleme blogu bu derste basliyor." %%| echo: false flowchart TD C["Ders 30: iki konu"] C --> A["Dal A - rank-1 tamamlama:<br/>A = uv^T, m+n-1 girdi, 2x2 det = 0"] C --> B["Dal B - sirkulant:<br/>ilk kolon belirler, C = polinom(P), P^n = I"] A --> A1["bipartite graph dongusuz<br/><=> tamamlanabilir"] B --> B1["carpim = cyclic convolution (grup)"] B --> B2["ozvektorler = birim kokleri -> Fourier"] K1["D1 uv^T dis-carpim"] K2["D16 Netflix tamamlama"] K3["D31 Fourier matrisi (sonraki)"] K4["CNN/evrisim (D32, fast.ai L15)"] N["D28-29 kayitsiz lab —<br/>sinyal-isleme blogu burada basliyor"] K1 --> A K2 --> A B2 --> K3 B1 --> K4 classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff; classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff; classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330; classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff; class C merkez; class A,B,A1,B1,B2 dal; class K1,K2,K3,K4 vec; class N teal; ``` @fig-kavram-haritasi-l30 dersin iskeletini gösterir: merkezdeki "iki konu" fikrinden iki dala ayrılır — Dal A (rank-1 tamamlama: $A = uv^{\top}$, $m+n-1$ girdi yeter, her 2×2 alt-determinant sıfır; bipartite graph döngüsüz ise tamamlanabilir) ve Dal B (sirkülant: ilk kolon tüm matrisi belirler, $C = $ polinom$(P)$, $P^n = I$; çarpım = cyclic convolution grup işlemi; özvektörler birim kökleri → Fourier); köprü düğümleri D1 $uv^{\top}$ dış-çarpım, D16 Netflix tamamlama, D31 Fourier matrisi (sonraki) ve CNN/evrişim (D32, fast.ai L15) iki dalı önceki ve sonraki derslere bağlar; ayrı bir teal düğüm D28-29 kayıtsız lab oturumlarını işaretler — sinyal-işleme bloğu burada başlar. ::: {.callout-tip title="Builder Notu — İki Konu Tek Köprü"} Bu ders iki bağımsız gibi görünen konuyu tek bir derste topluyor; ama ikisi de **yapı → cebir** köprüsünün örneği. ML köprüsü: rank-1 tamamlama, Ders 16'nın Netflix matris tamamlamasının kombinatoryal/yapısal versiyonudur (hangi gözlem desenleri tamamlamaya izin verir?); sirkülant matrisler ise evrişimin (CNN, Ders 32) ve FFT'nin (Ders 31) lineer-cebir temelidir. **Geriye köprü:** Ders 1 ($uv^{\top}$ dış-çarpım, kolon×satır), Ders 16 (matris tamamlama/nuclear norm), Ders 4 (özvektör). İleriye: Ders 31 (Fourier — sonraki). Tek cümle: Rank-1 matris tamamlama bir bipartite graph'ın döngüsüz olmasıyla mümkündür; sirkülant matrisler ise tek bir döngüsel kaydırma P'nin polinomudur, çarpımları döngüsel evrişimdir ve özvektörleri birim kökleridir (Fourier). ::: ## Rank-1 Matris Tamamlama Problemi {#sec-rank1-tamamlama} İlk konu, Prof. Rao'nun lab'ından doğan bir soru: > *"...can you complete it to a rank 1 matrix?" — Strang, 1:22* Bir matrisin bazı girdileri verilmiş (geri kalanı boş). Boşları, sonuç **rank-1** olacak şekilde doldurabilir misin? Rank-1 matris dış-çarpımdır (Ders 1): $$A = uv^{\top}, \qquad a_{ij} = u_i\,v_j$$ Kaç girdi serbestçe verilebilir? $m$ tane $u$, $n$ tane $v$ var; ama $u$'yu yeniden ölçekleyip $u_1 = 1$ yapabiliriz (bir serbestlik tekrarlı). Yani **$m + n - 1$** serbest parametre. $m = n = 3$ için 5 girdi. Bu girdiler sıfırdan farklı olmalı (sıfır verilen bir konum, o satır/sütunu sıfıra zorlardı). Bu beş girdinin nasıl zincirleme dokuz girdiye açıldığını @fig-tamamlama-zinciri bir sonraki bölümde sayılarla gösterir. ::: {.callout-tip title="Builder Notu — Dış-Çarpımın Geri Dönüşü"} "Rank-1 = $uv^{\top}$, $m+n-1$ serbestlik" Ders 1'in dış-çarpım görüşünün geri dönüşü. ML köprüsü: bu, Ders 16'nın Netflix matris tamamlamasının (eksik kullanıcı-film matrisini düşük-rank doldur) kombinatoryal/yapısal versiyonu — hangi gözlem desenleri tamamlamaya izin verir? Öneri sistemlerinde "hangi girdiler yeterli?" sorusu. ::: ## 2×2 Determinant Kuralı {#sec-2x2-det} Rank-1 olmanın testi: **her 2×2 alt-matris tekildir** (determinantı sıfır). Çünkü rank-1'de tüm kolonlar bir kolonun katı, tüm satırlar bir satırın katı: $$\det\begin{bmatrix} a_{ij} & a_{ik} \\ a_{lj} & a_{lk} \end{bmatrix} = 0 \quad (\text{her } 2\times2)$$ Bu, boş girdileri doldurmanın anahtarı: bir 2×2'nin üç girdisi biliniyorsa, dördüncüsü determinantı sıfır yapacak **tek** değerdir ($a_{ik} = a_{ij}\cdot a_{lk}/a_{lj}$). Bilinen girdilerden başlayıp 2×2 kuralıyla komşuları zincirleme doldurursun. ```{python} #| label: fig-tamamlama-zinciri #| fig-cap: "Beş girdiden dokuz girdi: 2×2 det=0 kuralı zincirleme her boşluğu TEK değerle doldurur — solda verilen m+n−1 = 5 girdilik ağaç deseni, ortada a₂₂ = a₁₂·a₂₁/a₁₁ kuralı (det=0 → tek değer), sağda 9/9 geri kazanılmış A_hat (maxdiff 2.2e-16, tüm 2×2 det ≈ 0)." #| fig-width: 11.5 #| fig-height: 3.8 #| code-fold: true from matplotlib.patches import Rectangle u, v, A = make_rank1(3, 3, seed=30) pos = tree_pattern(3, 3) A_hat = rank1_complete({p: A[p] for p in pos}, 3, 3) fig, axes = plt.subplots(1, 3, figsize=(11.5, 3.8)) # --- Sol: verilen 5 girdi (agac deseni) --- ax = axes[0] M = np.full((3, 3), np.nan) for (i, j) in pos: M[i, j] = A[i, j] Mm = np.ma.masked_invalid(M) cmap = NAVY_CMAP cmap.set_bad(color="#ffffff") vmin = float(np.nanmin(M)); vmax = float(np.nanmax(M)) text_thresh = vmin + 0.62 * (vmax - vmin) ax.imshow(Mm, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal") for i in range(3): for j in range(3): if not np.isnan(M[i, j]): v_ = M[i, j] ax.text(j, i, "{:.2f}".format(v_), ha="center", va="center", color="#ffffff" if v_ >= text_thresh else COL_TEXT, fontsize=11, fontweight="bold") else: ax.text(j, i, "?", ha="center", va="center", color="#999999", fontsize=15, fontweight="bold") ax.set_xticks(range(3)); ax.set_yticks(range(3)) ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) ax.set_title("verilen: m+n-1 = 5 girdi (agac)", color=COL_TEXT, fontsize=12, fontweight="bold") # --- Orta: 2x2 kurali semasi --- ax = axes[1] B = np.array([[A_hat[0, 0], A_hat[0, 1]], [A_hat[1, 0], A_hat[1, 1]]]) vmin2 = float(np.min(B)); vmax2 = float(np.max(B)) if abs(vmax2 - vmin2) < 1e-12: vmax2 = vmin2 + 1.0 tt2 = vmin2 + 0.62 * (vmax2 - vmin2) ax.imshow(B, cmap=NAVY_CMAP, vmin=vmin2, vmax=vmax2, aspect="equal") for i in range(2): for j in range(2): v_ = B[i, j] ax.text(j, i, "{:.2f}".format(v_), ha="center", va="center", color="#ffffff" if v_ >= tt2 else COL_TEXT, fontsize=12, fontweight="bold") ax.add_patch(Rectangle((0.5, 0.5), 1.0, 1.0, fill=False, edgecolor=COL_VEC3, lw=3)) ax.text(0.5, -0.85, "a22 = a12*a21/a11", ha="center", va="center", color=COL_TEXT, fontsize=11, fontweight="bold") ax.text(0.5, 1.85, "det = 0 -> TEK deger", ha="center", va="center", color=COL_VEC3, fontsize=11, fontweight="bold") ax.set_xlim(-0.5, 1.5); ax.set_ylim(2.1, -1.1) ax.axis("off") # --- Sag: tamamlanmis A_hat tam heatmap --- heatmap(axes[2], A_hat, title="tamamlandi: 9/9, maxdiff 2.2e-16", cmap=NAVY_CMAP, annotate=True, fmt="{:.2f}", fontsize=11) fig.suptitle("Bes girdiden dokuz girdi: 2x2 det=0 kurali zincirleme her boslugu TEK degerle " "doldurur (maxdiff 2.2e-16, tum 2x2 det = 0)", fontsize=12.5, fontweight="bold", color=COL_TEXT, y=1.06) plt.tight_layout() plt.show() ``` @fig-tamamlama-zinciri solda verilen 5 girdilik ağaç desenini (satır-0 + kolon-0; boş hücreler "?"), ortada $a_{22} = a_{12}\cdot a_{21}/a_{11}$ kuralını (det=0 → tek değer, turuncu vurgu), sağda tamamlanmış $A_{\text{hat}}$'ı gösterir: beş girdiden başlayıp 2×2 det=0 kuralını zincirleyerek dokuz girdinin tamamı geri kazanılır, maxdiff $2.2\times10^{-16}$ ve $A_{\text{hat}}$'ın tüm 2×2 determinantları $\approx 0$. 4×5'te de 8 girdiden 20 girdi aynı kesinlikle gelir. ::: {.callout-tip title="Builder Notu — Rank'ı Küçük Pencerelerden Oku"} "Rank-1 ⟺ tüm 2×2 det = 0" rank'ın yerel karakterizasyonu: rankı global SVD'den değil, küçük determinantlardan oku. ML köprüsü: bu kural, matris tamamlamanın neden bazı desenlerde benzersiz (her boşluk tek değer) bazılarında imkânsız (çelişen kısıtlar) olduğunu açıklar — düşük-rank tamamlamanın belirlenebilirlik (identifiability) koşulu. ::: ## Bipartite Graph ve Tamamlanabilirlik {#sec-bipartite} Hangi konumlar tamamlamaya izin verir? Bir kombinatorikçinin görüşü: problemi bir **bipartite graph**a (iki-parçalı çizge) çevir. > *"...this is called a bipartite graph." — Strang, 12:02* Satırları bir parça ($m$ düğüm), sütunları diğer parça ($n$ düğüm) yap. Verilen her $(i,j)$ girdisi, satır-$i$ ile sütun-$j$ arasına bir **kenar** koyar. $m+n-1$ girdi → $m+n-1$ kenar. Kural: matris tamamlanabilir ⟺ bu graf **döngüsüzdür** (cycle yok, yani bir orman/ağaç). Bir döngü, tüm girdileri verilmiş bir 2×2 (veya daha büyük) demektir — orada determinantı sıfır zorlayamazsın, çelişki çıkar. $$\text{tamamlanabilir} \iff \text{bipartite graph dongusuz (forest)}$$ Döngüsüz graf, 2×2 kuralını çelişkisiz zincirlemene izin verir; her boş girdi tek değerle belirlenir. ```{python} #| label: fig-bipartite #| fig-cap: "Tamamlanabilirlik saf graf sorusu: kenarlar döngü kapatıyorsa determinantı sıfır zorlayamazsın — motor çelişkiyi yakalar" #| fig-width: 9.5 #| fig-height: 4.2 #| code-fold: true fig, axes = plt.subplots(1, 2, figsize=(9.5, 4.2)) # Sol: ağaç (forest) deseni — 5 kenar mavi draw_bipartite(axes[0], tree_pattern(3, 3), 3, 3, title="döngüsüz (forest) -> tamamlanabilir") # Sağ: döngü deseni — 4 kenar turuncu cyc = [(0, 0), (0, 1), (1, 0), (1, 1)] draw_bipartite(axes[1], cyc, 3, 3, edge_colors=[COL_VEC3]*4, title="döngü r1-c1-r2-c2 -> çelişki riski") axes[1].text(0.5, -0.02, "değerler 2,6,1,5: det = 2*5-6*1 = 4 != 0 -> İMKANSIZ (motor: None)", ha="center", va="top", color=COL_TEXT, fontsize=8.5) fig.suptitle("Tamamlanabilirlik saf graf sorusu: kenarlar döngü kapatıyorsa determinantı sıfır zorlayamazsın — motor çelişkiyi yakalar", color=COL_TEXT, fontsize=10.5, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.95]) plt.show() ``` @fig-bipartite solda döngüsüz (forest) ağaç desenini gösterir — beş kenar bir orman oluşturur, tamamlanabilir; sağda $(1,1),(1,2),(2,1),(2,2)$ kenarları bir döngü kapatır (r1-c1-r2-c2). Bu döngüde değerler $2,6,1,5$ verilince det $= 2\cdot5 - 6\cdot1 = 4 \neq 0$ olduğundan rank-1 tamamlama **imkânsızdır** (motor `None` döner); determinantı sıfır zorlayamazsın. ::: {.callout-tip title="Builder Notu — Cebir Graf Olunca"} "Tamamlanabilir ⟺ bipartite graph döngüsüz" zarif bir cebir-graf köprüsü: matris yapısı (rank-1 doldurulabilirlik) saf grafik teorisine (döngü var mı?) indirgenir. ML köprüsü: graf-tabanlı düşünme öneri sistemlerinde merkezî — kullanıcı-ürün bipartite grafı, eksik kenarları (tahmin) tamamlamak; döngü/bağlılık yapısı hangi tahminlerin güvenilir olduğunu belirler. Cebir ↔ graf çevirisi Phase 2'nin tekrarlayan teması. ::: ## Sirkülant Matris ve Cyclic Shift P {#sec-sirkulant-P} İkinci konu: **sirkülant** (dolaşımlı) matris. Her kolon, bir öncekinin **döngüsel kaydırılmışı**dır — yani ilk kolonu verirsen tüm matris belli. Anahtar yapı taşı döngüsel kaydırma matrisi P: > *"...the key matrix in this is really a cyclic shift matrix." — Strang, 28:21* $$P = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$ P bir vektörü bir aşağı kaydırır, en alttaki döngüsel olarak tepeye döner. P bir permütasyon matrisidir. $P^2$ iki kaydırma, $P^3$ üç kaydırma. P'nin kuvvetlerinin bir sonraki bölümde $P^4 = I$ ile başa döndüğünü @fig-cyclic-shift gösterir. ::: {.callout-tip title="Builder Notu — Bir Kolon Bütün Matris"} "İlk kolon → tüm matris, cyclic shift P" sirkülantın sıkıştırılmış temsili: $n\times n$ matris yerine $n$ sayı (ilk kolon). ML köprüsü: bu, evrişimin (convolution) matris hâlidir — bir filtreyi tüm konumlara kaydırarak uygula; CNN'in ağırlık paylaşımı (weight sharing) tam bu döngüsel/kaydırmalı yapı. Toeplitz matrisi (Ders 32) sirkülantın döngüsüz akrabasıdır. ::: ## C = Polinom(P), Pⁿ = I {#sec-polinom-P} Her sirkülant matris, P'nin bir **polinomu**dur (köşegenlere $c_0, c_1, c_2, c_3$ koymak = P kuvvetlerinin kombinasyonu): > *"...every circulant matrix is a polynomial in P..." — Strang, 32:45* $$C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$$ Kritik özellik: $n\times n$'de **$P^n = I$** ($n$ kaydırma başa döner). Yani P'nin kuvvetleri $\{I, P, \dots, P^{n-1}\}$ ile sınırlı — derecesi $n$'i aşan terimler döngüsel olarak geri sarar. Bu sayede sirkülantlar bir **grup** oluşturur: iki sirkülantın çarpımı (iki polinomun çarpımı) yine bir sirkülanttır ($P^n=I$ ile dereceyi $n$'in altında tutarak). ```{python} #| label: fig-cyclic-shift #| fig-cap: "Döngüsel kaydırma P permütasyondur; P^4 = I — kuvvetler {I, P, P^2, P^3} ile sınırlı; sirkülant C = c0 I + c1 P + c2 P^2 + c3 P^3 olarak bu dört kuvvetin doğrusal birleşimidir." #| fig-width: 11.5 #| fig-height: 3.2 #| code-fold: true P = cyclic_P(4) mats = [P, P @ P, np.linalg.matrix_power(P, 3), np.linalg.matrix_power(P, 4)] titles = ["P (1 kaydırma)", "P^2", "P^3", "P^4 = I (başa döndü)"] fig, axes = plt.subplots(1, 4, figsize=(11.5, 3.2)) for ax, M, t in zip(axes, mats, titles): heatmap(ax, M, title=t, fmt="{:.0f}") fig.suptitle( "Döngüsel kaydırma P permütasyondur; P^4 = I — kuvvetler {I, P, P^2, P^3} ile sınırlı; " "sirkülant C = c0 I + c1 P + c2 P^2 + c3 P^3", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.93]) plt.show() ``` @fig-cyclic-shift $P, P^2, P^3, P^4$ kuvvetlerini sırayla gösterir: her kaydırma 1'leri bir köşegen ilerletir ve $P^4 = I$ başa döner. Demek ki P'nin kuvvetleri $\{I, P, P^2, P^3\}$ ile sınırlıdır; sirkülant $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$ tam bu dört kuvvetin doğrusal birleşimidir. Motor tanığı: P döngüsel kaydırma, $P^4 = I$, $P^3 \neq I$ ve $P\cdot(1,2,3,4) = (4,1,2,3)$ (bir aşağı, sarmalı). ::: {.callout-tip title="Builder Notu — Matris Dünyasından Polinom Dünyasına"} "Sirkülant = polinom($P$), $P^n=I$" cebirsel kalbi: matris dünyasını polinom dünyasına çevirir. ML köprüsü: bu, evrişimin neden polinom çarpımı (ve Fourier'de basit çarpma) olduğunu açıklar; $P^n=I$ döngüselliği, ayrık Fourier dönüşümünün (DFT, Ders 31) periyodikliğinin kaynağı. Polinom ↔ matris ↔ sinyal üç dil aynı şey. ::: ## Cyclic Convolution {#sec-cyclic-conv} Sirkülant çarpımı, polinom çarpımıdır — yani **evrişim** (convolution). Örnek: $(3,1,2) \circledast (4,6,1)$, gizli polinomlar $(3 + x + 2x^2)(4 + 6x + x^2)$: $$(3, 1, 2) * (4, 6, 1) = (12, 22, 17, 13, 2)$$ (İlkokul çarpması: terim terim çarp-topla.) Sirkülantlarda $P^n = I$ olduğundan **döngüsel** (cyclic) evrişim: taşan terimler başa sarar. > *"...I'm just doing cyclic convolution actually." — Strang, 36:48* $$(3, 1, 2) \circledast (4, 6, 1) = (12+13,\ 22+2,\ 17) = (25, 24, 17)$$ $n=3$'te $P^3=I$, böylece 5-uzunluklu sonuç 3'e sarılır. Hoş bir sağlama: rakam-toplamları çarpımı korunur — $(3+1+2)(4+6+1) = 6\cdot11 = 66 = 25+24+17$. Matris çarpımı = döngüsel evrişim = polinom çarpımı (mod $P^n-1$). ```{python} #| label: fig-konvolusyon #| fig-cap: "Sirkülant çarpımı = polinom çarpımı = cyclic convolution: taşan terimler P^n = I ile başa sarar — (3,1,2) çark (4,6,1) = (25,24,17). Doğrusal evrişim (12,22,17,13,2); taşan son iki terim 13 ve 2 başa sarınca döngüsel sonuç (25,24,17). Sağlama: 6*11 = 66 = 25+24+17." #| fig-width: 12 #| fig-height: 4 #| code-fold: true c = np.array([3., 1, 2]); d = np.array([4., 6, 1]) lin = linear_conv(c, d) # (12,22,17,13,2) cyc = cyclic_conv(c, d) # (25,24,17) C = circulant(c) # ilk kolon (3,1,2) fig, axes = plt.subplots(1, 3, figsize=(12, 4)) # Sol: C = circulant(3,1,2) heatmap heatmap(axes[0], np.array(C, dtype=float), title="C: ilk kolon (3,1,2) tümünü belirler", fmt="{:.0f}") # Orta: doğrusal evrişim 5 bar — ilk üç navy, son iki turuncu + sarmalama okları ax = axes[1] bar_colors = [COL_PRIMARY, COL_PRIMARY, COL_PRIMARY, COL_VEC3, COL_VEC3] xs = np.arange(len(lin)) ax.bar(xs, lin, color=bar_colors, edgecolor=COL_TEXT, linewidth=0.8, zorder=3) for x, v in zip(xs, lin): ax.text(x, v + 0.5, f"{v:.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold") ax.annotate("13 -> +12 ye sarar", xy=(3, 13.3), xytext=(0.55, 24.0), arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.8), color=COL_VEC3, fontsize=8.5, fontweight="bold") ax.annotate("2 -> +22 ye sarar", xy=(4, 2.3), xytext=(1.6, 13.5), arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.8), color=COL_VEC3, fontsize=8.5, fontweight="bold") ax.set_title("doğrusal: (12,22,17,13,2)", color=COL_TEXT, fontsize=12, fontweight="bold") ax.set_ylim(0, 26) ax.set_xticks(xs) apply_style(ax) # Sağ: döngüsel sonuç 3 bar navy (25,24,17) + sağlama metni ax = axes[2] xs2 = np.arange(len(cyc)) ax.bar(xs2, cyc, color=COL_PRIMARY, edgecolor=COL_TEXT, linewidth=0.8, zorder=3) for x, v in zip(xs2, cyc): ax.text(x, v + 0.5, f"{v:.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold") ax.text(0.5, 0.92, "sağlama: 6*11 = 66 = 25+24+17", transform=ax.transAxes, ha="center", va="top", color=COL_TEXT, fontsize=9.5, fontweight="bold", bbox=dict(boxstyle="round,pad=0.3", facecolor=COL_BG, edgecolor=COL_STEEL_300)) ax.set_title("döngüsel (P^3 = I): (25,24,17)", color=COL_TEXT, fontsize=12, fontweight="bold") ax.set_ylim(0, 30) ax.set_xticks(xs2) apply_style(ax) fig.suptitle("Sirkülant çarpımı = polinom çarpımı = cyclic convolution: taşan terimler P^n = I ile başa sarar", color=COL_TEXT, fontsize=12.5, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.95]) plt.show() ``` @fig-konvolusyon solda $C = \text{circulant}(3,1,2)$ heatmap'ini (ilk kolon tümünü belirler), ortada doğrusal evrişimi $(12,22,17,13,2)$ — taşan son iki terim $13$ ve $2$ turuncu, sarmalama okları $13 \to +12$ ve $2 \to +22$ — ve sağda döngüsel sonucu $(25,24,17)$ gösterir. Sağlama: $6\cdot11 = 66 = 25+24+17$. Taşan terimler $P^n = I$ ile başa sarar; matris çarpımı = polinom çarpımı = cyclic convolution. ::: {.callout-tip title="Builder Notu — Üç Dilin Aynı Çarpımı"} "Sirkülant çarpımı = cyclic convolution = polinom çarpımı" üç dilin birliği. ML köprüsü: CNN'lerin (Ders 32) konvolüsyon katmanı tam budur; fast.ai L15'in im2col/conv2d'si konvolüsyonu matris çarpımına çevirir. FFT (Ders 31) konvolüsyonu $O(n \log n)$'de yapar — sinyal işleme ve büyük-çekirdek CNN'lerin hızı buradan. ::: ## Özvektörler = Birim Kökleri (Fourier) {#sec-ozvektorler-fourier} Sirkülant C'nin özvektörleri ne? C = P'nin polinomu olduğundan, **C'nin özvektörleri P'nin özvektörleriyle aynı** (P'nin özvektörü, $P^2$'nin ve $P^3$'ün de özvektörü): > *"...the eigenvectors of C are the same as the eigenvectors of P." — Strang, 45:01* Demek ki tek soru: P'nin özvektörleri/özdeğerleri ne? P döngüsel kaydırma; özdeğerleri **birim kökleri** (roots of unity). $n=4$ için $(1,1,1,1) \to \lambda=1$; $(1,-1,1,-1) \to \lambda=-1$; ve karmaşık $(1, i, -1, -i) \to \lambda=i, \lambda=-i$: > *"...the eigenvectors are the four roots of 1." — Strang, 48:42* $$\lambda(P) = 1, -1, i, -i = e^{2\pi i k/n}, \quad k = 0, 1, 2, 3$$ Özvektörler birim köklerinden kurulur — bunlar **Fourier matrisinin** kolonlarıdır (Ders 31). Yani TÜM sirkülantlar aynı özvektörleri (Fourier) paylaşır. ```{python} #| label: fig-fourier-ozvektor #| fig-cap: "TÜM sirkülantların özvektörleri aynı: birim köklerinden kurulan Fourier kolonları — evrişim çarpmaya döner (Ders 31). Sol: $\\lambda(P)$ birim çemberdeki dördüncü birim kökleri. Orta: $F^{-1}CF$ köşegen (off-diag 5.8e-16). Sağ: iki farklı sirkülant AYNI $F$'de köşegenleşir, köşegen = FFT(c)." #| fig-width: 12 #| fig-height: 4 #| code-fold: true fig, axes = plt.subplots(1, 3, figsize=(12, 4)) # Sol: birim cember + 4 kok ax = axes[0] theta = np.linspace(0, 2*np.pi, 200) ax.plot(np.cos(theta), np.sin(theta), color=COL_STEEL_300, lw=1.0, zorder=1) roots = [(1, 0), (0, 1), (-1, 0), (0, -1)] labels = ["1", "i", "-1", "-i"] for (x, y), lab in zip(roots, labels): ax.scatter([x], [y], s=120, color=COL_PRIMARY, zorder=3) ax.annotate(lab, (x, y), textcoords="offset points", xytext=(10, 10), color=COL_TEXT, fontsize=12, fontweight="bold") ax.axhline(0, color=COL_STEEL_300, lw=0.8); ax.axvline(0, color=COL_STEEL_300, lw=0.8) ax.set_title(r"$\lambda(P) = $ birim kökleri $e^{2\pi i k/4}$", color=COL_TEXT, fontsize=12, fontweight="bold") ax.set_xlim(-1.4, 1.4); ax.set_ylim(-1.4, 1.4) apply_style(ax); ax.set_aspect("equal") # Orta: F^-1 C F kosegen heatmap ax = axes[1] F = fourier_matrix(4) rng = np.random.default_rng(30) c4 = rng.uniform(-2, 2, 4) C4 = circulant(c4) off, diag = diag_offmax(F, C4) heatmap(ax, np.abs(np.linalg.solve(F, C4 @ F)), title=r"$F^{-1} C F$ köşegen (off-diag 5.8e-16)", fmt="{:.2f}") # Sag: iki farkli sirkulant kosegen bar ax = axes[2] d1 = np.abs(np.fft.fft(c4)) d2 = np.abs(np.fft.fft(c4*2 + 1)) x = np.arange(4) ax.bar(x - 0.18, d1, width=0.36, color=COL_PRIMARY, label="C1") ax.bar(x + 0.18, d2, width=0.36, color=COL_VEC3, label="C2") ax.annotate("köşegen = FFT(c) — Ders 31", xy=(0.46, 0.93), xycoords="axes fraction", ha="center", color=COL_TEXT, fontsize=9, fontweight="bold") ax.set_title(r"farklı $C$'ler AYNI $F$'de köşegenleşir", color=COL_TEXT, fontsize=12, fontweight="bold") ax.set_xticks(x); ax.legend(loc="upper right") apply_style(ax) fig.suptitle("TÜM sirkülantların özvektörleri aynı: birim köklerinden kurulan Fourier kolonları — evrişim çarpmaya döner (Ders 31)", color=COL_TEXT, fontsize=12, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` @fig-fourier-ozvektor solda $\lambda(P)$'yi birim çemberdeki dört birim kökü ($1, i, -1, -i$) olarak, ortada $F^{-1}CF$'in köşegen olduğunu (köşegen-dışı $5.8\times10^{-16}$), sağda iki FARKLI sirkülantın AYNI $F$'de köşegenleştiğini (köşegen $= \text{FFT}(c)$, Ders 31) gösterir. Motor tanığı: $F^{-1}CF$ köşegen-dışı $5.8\times10^{-16}$, köşegen $= \text{np.fft.fft}(c)$ birebir, ve farklı sirkülant da aynı $F$'de köşegenleşir (ortak özvektör tabanı). Bu dersin son sorusu — sirkülant özvektörünü P ile çarpınca hangi özdeğer çıkar — Egzersiz 4'te somutlaşır; @fig-egz4-ozvektor motor cevabını verir. ```{python} #| label: fig-egz4-ozvektor #| fig-cap: "Egzersiz 4 motor cevabı: P(1,i,-1,-i) = -i (1,i,-1,-i) — aşağı-kaydırmada lambda = -i; eşlenik kolon (1,-i,-1,i) +i alır. Sol panelde x bileşenleri (navy) ve Px bileşenleri (turuncu kesik) her biri -90° dönmüş; sağ panelde |Px - (-i)x| = 0 (tam tutar) ile |Px - (+i)x| = 2 (tutmaz) karşılaştırması." #| fig-width: 9 #| fig-height: 3.8 #| code-fold: true x = np.array([1, 1j, -1, -1j]) Px = cyclic_P(4) @ x fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9, 3.8)) # Sol: karmaşık düzlemde 4 bileşen — x (navy ok) ve Px (turuncu kesik ok) theta = np.linspace(0, 2*np.pi, 200) ax1.plot(np.cos(theta), np.sin(theta), color=COL_STEEL_300, linewidth=1.0, alpha=0.7) for i in range(4): ax1.annotate("", xy=(x[i].real, x[i].imag), xytext=(0, 0), arrowprops=dict(arrowstyle="-|>", color=COL_PRIMARY, lw=2.0)) ax1.annotate("", xy=(Px[i].real, Px[i].imag), xytext=(0, 0), arrowprops=dict(arrowstyle="-|>", color=COL_VEC3, lw=1.6, linestyle="--")) labels = ["x1", "x2", "x3", "x4"] for i in range(4): ax1.text(x[i].real*1.18, x[i].imag*1.18, labels[i], color=COL_PRIMARY, fontsize=11, ha="center", va="center", fontweight="bold") ax1.set_xlim(-1.5, 1.5); ax1.set_ylim(-1.5, 1.5) ax1.set_xlabel("gerçek"); ax1.set_ylabel("sanal") ax1.set_title("P her bileşeni -90 derece döndürür") apply_style(ax1); ax1.set_aspect("equal") # Sağ: iki hata barı — λ = -i tam tutar (0), λ = +i tutmaz (2) err_neg = np.max(np.abs(Px - (-1j)*x)) err_pos = np.max(np.abs(Px - (1j)*x)) bars = ax2.bar([0, 1], [err_neg, err_pos], color=[COL_PRIMARY, COL_VEC3], width=0.6) ax2.set_xticks([0, 1]) ax2.set_xticklabels(["|Px - (-i)x| = 0", "|Px - (+i)x| != 0"]) ax2.set_ylabel("maksimum hata") ax2.set_title("lambda = -i (i DEĞİL) [motor notu]") for b, v in zip(bars, [err_neg, err_pos]): ax2.text(b.get_x()+b.get_width()/2, v+0.05, f"{v:.1f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold") ax2.set_ylim(0, 2.4) apply_style(ax2) fig.suptitle("Egzersiz 4 motor cevabı: P(1,i,-1,-i) = -i (1,i,-1,-i) — aşağı-kaydırmada lambda = -i; eşlenik kolon (1,-i,-1,i) +i alır", color=COL_TEXT, fontsize=10) fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` @fig-egz4-ozvektor solda $x = (1, i, -1, -i)$ bileşenlerini (navy) ve $Px$ bileşenlerini (turuncu kesik) gösterir — P her bileşeni $-90°$ döndürür; sağda iki hata barı $|Px - (-i)x| = 0$ (tam tutar) ile $|Px - (+i)x| \neq 0$ ($= 2$, tutmaz) karşılaştırır. ::: {.callout-note title="motor notu — Egz4 özdeğeri ve §7'deki iki kök"} Notion §7'deki "$(1, i, -1, -i) \to \lambda=i, \lambda=-i$" cümlesi iki karmaşık özdeğeri birden anar (P'nin spektrumunda hem $+i$ hem $-i$ vardır) ve Egzersiz 4 "(i ile mi?)" sorusunu açık bırakır. Bu aşağı-kaydırma P (yani $(Px)_i = x_{(i-1)\bmod n}$) için motor cevabı kesindir: $x = (1, i, -1, -i)$ özvektörünün özdeğeri **$\lambda = -i$**'dir ($i$ DEĞİL) — $P\cdot x = -i\cdot x$. Eşlenik kolon $(1, -i, -1, i)$ ise $\lambda = +i$ alır. İki kök birden P'nin spektrumunda yaşar; ama bu spesifik kolon-özvektör eşleşmesi $(1, i, -1, -i) \mapsto -i$ şeklindedir. ::: ::: {.callout-tip title="Builder Notu — Bütün Sirkülantların Ortak Tabanı"} "Tüm sirkülantların özvektörleri = Fourier" sinyal işlemenin temel teoremi: Fourier tabanında her sirkülant köşegenleşir, evrişim çarpmaya döner. ML köprüsü: bu, FFT'nin (Ders 31) ve frekans-uzayı filtrelemenin temeli; konvolüsyon teoremi (zaman uzayında evrişim = frekans uzayında çarpma) doğrudan buradan. Graf sinyal işleme (NYU spektral GCN, Ders 19/35) bu fikri graf Laplacian özvektörlerine genelleştirir. Köşegen değerleri tam $\text{FFT}(c)$ olduğundan, Ders 31'in $F^{-1}CF = \text{diag}(\text{FFT}(c))$ köprüsü buradan açılır. ::: ## Bu Dersin Özeti {#sec-ozet-d30} - **Rank-1 tamamlama:** $A = uv^{\top}$, $a_{ij} = u_i v_j$; $m+n-1$ serbest parametre. Rank-1 ⟺ tüm 2×2 det = 0. - **Bipartite graph:** satır+sütun düğüm, girdi=kenar; tamamlanabilir ⟺ döngüsüz (forest). - **Sirkülant C:** ilk kolon tümünü belirler; cyclic shift P; $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$; $P^n = I$. - **Grup + cyclic convolution:** iki sirkülantın çarpımı sirkülant; çarpım = döngüsel evrişim = polinom çarpımı (mod $P^n-1$). - **Özvektörler:** C'nin özvektörleri = P'nin özvektörleri = birim kökleri ($1, -1, i, -i$ for $n=4$) = Fourier matrisi. - **Tüm sirkülantlar aynı özvektörleri (Fourier) paylaşır** → evrişim çarpmaya döner (Ders 31). ::: {.callout-important title="Tek Bir Cümle"} Rank-1 matris tamamlama bir bipartite graph'ın döngüsüz olmasıyla mümkündür (her boş girdi 2×2 det=0 ile tek değer alır); sirkülant matrisler ise tek bir döngüsel kaydırma P'nin polinomudur, çarpımları döngüsel evrişimdir ve özvektörleri birim kökleridir — yani hepsi Fourier matrisinde köşegenleşir. ::: ## Kontrol Soruları {#sec-sorular-d30} ::: {.callout-note collapse="true" title="Soru 1 — Kaç girdi serbest ve rank-1'in testi"} **Soru:** Rank-1 matris tamamlamada kaç girdi serbestçe verilebilir ve rank-1'in testi nedir? **Cevap:** $m+n-1$ girdi ($A = uv^{\top}$'de $m$ tane $u$ + $n$ tane $v$, ama $u_1=1$ normalize edilince bir serbestlik düşer). Verilen girdiler sıfırdan farklı olmalı. Rank-1 testi: **tüm 2×2 alt-determinantlar sıfır** olmalı (tüm kolonlar bir kolonun katı). Bir 2×2'nin üç girdisi biliniyorsa, dördüncüsü det=0 yapacak tek değerdir. ::: ::: {.callout-note collapse="true" title="Soru 2 — Bipartite graph tamamlanabilirliği nasıl belirler"} **Soru:** Bipartite graph rank-1 tamamlanabilirliği nasıl belirler? **Cevap:** Satırlar bir parça, sütunlar diğer parça düğümleri; verilen her $(i,j)$ girdisi satır-$i$ ↔ sütun-$j$ kenarı. Matris tamamlanabilir ⟺ bu graf **döngüsüzdür** (forest/ağaç). Döngü, tüm girdileri verilmiş bir alt-yapı demektir; orada determinantı sıfır zorlayamazsın (çelişki). Döngüsüz graf, 2×2 kuralını çelişkisiz zincirlemene izin verir. ::: ::: {.callout-note collapse="true" title="Soru 3 — Sirkülant neden P'nin polinomu ve neden grup"} **Soru:** Sirkülant matris neden P'nin polinomudur ve neden grup oluşturur? **Cevap:** Sirkülant C, köşegenlerinde $c_0, c_1, c_2, c_3$ taşır; bunlar tam olarak P kuvvetlerinin katsayılarıdır: $C = c_0 I + c_1 P + c_2 P^2 + c_3 P^3$ (P = döngüsel kaydırma). $P^n = I$ ($n$ kaydırma başa döner) olduğundan, iki sirkülantın çarpımı (iki polinomun çarpımı) yine $n$'den küçük dereceli bir polinom = sirkülanttır. Bu yüzden grup: çarpım kapalı, I birim eleman. ::: ::: {.callout-note collapse="true" title="Soru 4 — Sirkülantın özvektörleri ve neden önemli"} **Soru:** Sirkülant matrisin özvektörleri nedir ve bu neden önemli? **Cevap:** C = P'nin polinomu olduğundan C'nin özvektörleri = P'nin özvektörleri. P döngüsel kaydırmanın özdeğerleri **birim kökleridir** ($e^{2\pi i k/n}$; $n=4$ için $1, -1, i, -i$), özvektörleri **Fourier matrisinin** kolonları. Önemli çünkü TÜM sirkülantlar aynı (Fourier) özvektörleri paylaşır — Fourier tabanında her sirkülant köşegenleşir, dolayısıyla **evrişim çarpmaya dönüşür** (konvolüsyon teoremi, FFT temeli, Ders 31). ::: ## Egzersizler {#sec-egzersizler-d30} 1. **2×2 tamamlama.** Bir 2×2 matrisin üç girdisi: $a_{11}=2$, $a_{12}=6$, $a_{21}=1$. Rank-1 olması için $a_{22}$ ne olmalı? (det=0 kuralı: $a_{22} = a_{12}\cdot a_{21}/a_{11}$.) (Motor tanığı: $a_{22} = 6\cdot1/2 = 3.0$.) 2. **Bipartite döngü.** 3×3 matriste $(1,1),(1,2),(2,1),(2,2)$ girdileri verilmiş. Bunu bipartite graf olarak çiz; bir döngü var mı? Rank-1 tamamlama mümkün mü, neden? (Motor tanığı: bu dört girdi r1-c1-r2-c2 döngüsü kapatır; değerler $2,6,1,5$ ile det $= 2\cdot5 - 6\cdot1 = 4 \neq 0$ → tamamlama **imkânsız** (motor `None`). Aynı döngü $2,6,1,3$ (det=0) ile çelişkisiz geçer, ama bu şans, kural değil; bkz. @fig-bipartite.) 3. **Cyclic convolution.** $(1, 2) \circledast (3, 4)$ döngüsel evrişimini ($n=2$, $P^2=I$) hesapla. (Önce normal evrişim $(1,2)*(3,4)$, sonra sarmala.) (Motor tanığı: doğrusal $(3, 10, 8)$ → döngüsel $(3+8, 10) = (11, 10)$; sağlama $3\cdot7 = 21 = 11+10$.) 4. **Sirkülant özvektör.** 4×4 cyclic shift P için $(1, i, -1, -i)$ vektörünü P ile çarp (bir aşağı kaydır, sarmala). Hangi $\lambda$ ile özvektör? (i ile mi?) (**[motor notu]:** Bu aşağı-kaydırma P için $P\cdot(1, i, -1, -i) = -i\cdot(1, i, -1, -i)$, yani $\lambda = -i$ — **$i$ DEĞİL**. Eşlenik kolon $(1, -i, -1, i)$ ise $\lambda = +i$ alır; bkz. @fig-egz4-ozvektor.) 5. **(Ders 31 habercisi)** Bu derste sirkülantların özvektörlerinin birim kökleri olduğunu gördük. Bu özvektörleri kolon kolon bir matrise dizersen ne elde edersin? $n\times n$ bu matrisin adı ne, hangi dönüşümü temsil eder? Bir tahmin yaz — Ders 31 "sirkülant matrislerin özvektörleri: Fourier matrisi"ni işliyor. (Motor tanığı: özvektörleri kolon kolon dizince $F^{-1}CF = \text{diag}(\text{np.fft.fft}(c))$, yani $F$ tüm sirkülantları köşegenleştirir — ortak özvektör tabanı.) ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d30} **Ders 31: Sirkülant Matrislerin Özvektörleri — Fourier Matrisi.** Bu dersin birim-kök özvektörlerini bir matrise dizince **Fourier matrisi** (F) çıkar; ayrık Fourier dönüşümü (DFT). Her sirkülant F'de köşegenleşir, evrişim çarpmaya döner (konvolüsyon teoremi), ve FFT bu yapıyı $O(n \log n)$'de hesaplar — sinyal işleme ve CNN'lerin matematiksel temeli. ::: {.callout-warning title="Hazırlık"} Bu dersin Egzersiz 5'inin sorduğu soruyu zihninde tut: sirkülantların birim-kök özvektörlerini kolon kolon bir matrise dizersen hangi matris çıkar? Ders 31, bu **Fourier matrisini** (F) tanımlar ve her sirkülantın $F^{-1}CF = \text{diag}(\text{FFT}(c))$ ile köşegenleştiğini gösterir — köşegen değerleri tam FFT(c). Bu, evrişimi çarpmaya çeviren konvolüsyon teoreminin, FFT'nin ($O(n \log n)$) ve sinyal-işleme/CNN bloğunun (Ders 32) matematiksel kalbidir. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d30} | Kavram | Formül / Fikir | Strang (dk) | |--------|----------------|-------------| | **Rank-1 tamamlama** | $A = uv^{\top}$; $m+n-1$ girdi; tüm 2×2 det = 0 | 1m22 | | Bipartite graph | satır/sütun düğüm, girdi=kenar; döngüsüz ⟺ tamamlanabilir | 12m02 | | Cyclic shift P | sirkülant: ilk kolon tümünü belirler | 28m21 | | C = polinom(P) | $c_0 I + c_1 P + c_2 P^2 + c_3 P^3$; $P^n = I$ | 32m45 | | Cyclic convolution | sirkülant çarpımı = döngüsel evrişim | 36m48 | | Özvektörler = P'nin | C = polinom(P) → aynı özvektörler | 45m01 | | Birim kökleri → Fourier | $\lambda(P) = 1, -1, i, -i = e^{2\pi i k/n}$ | 48m42 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d30} - **Sirkülant = evrişim = CNN:** sirkülant matrisle çarpmak döngüsel evrişim; CNN'in (Ders 32) ağırlık paylaşımı; fast.ai L15 im2col/conv2d aynı yapı. - **Özvektörler Fourier → FFT:** tüm sirkülantlar Fourier'de köşegenleşir; evrişim çarpmaya döner (konvolüsyon teoremi); FFT $O(n \log n)$ (Ders 31). - **Rank-1 tamamlama:** Ders 16 Netflix matris tamamlamasının kombinatoryal hali; bipartite graf döngüsü belirlenebilirliği verir. - **Cebir ↔ graf:** rank-1 doldurulabilirlik saf grafik teorisine (döngü var mı?) indirgenir; öneri sistemleri bipartite graf düşünür. - **Graf sinyal işleme:** sirkülant→Fourier fikri graf Laplacian özvektörlerine genelleşir (spektral GCN, NYU paralel, Ders 19/35). - **Geriye köprü:** Ders 1 ($uv^{\top}$ dış-çarpım), Ders 16 (matris tamamlama/nuclear norm), Ders 4 (özvektör). Paralel: fast.ai L15 (convolution), NYU H6 (CNN). ::: {.callout-important title="Kapanış"} > *"...the eigenvectors of C are the same as the eigenvectors of P." — Strang, 45:01* Tüm sirkülantlar tek bir özvektör tabanını (Fourier) paylaşır; bu, evrişimi çarpmaya çeviren konvolüsyon teoreminin ve tüm sinyal işlemenin kalbidir — sinyal/CNN bloğunun açılışı. :::