30 Sirkülant Matrislerin Özvektörleri — Fourier Matrisi

Toeplitz ve sirkülant evrişim, normal matris ailesi ve dünyanın en önemli kompleks matrisi

Bölüm bilgisi

Bu ders, Ders 30’un sirkülantlarının özvektörlerini somutlaştırır: Fourier matrisi F. Tüm sirkülantlar aynı özvektör matrisini paylaşır — bu, ayrık Fourier dönüşümü (DFT) ve FFT’nin temelidir. Strang’in Ders 31 videosu (≈52 dk) ve OCW Lecture 31 temel alınmıştır. Okuma süresi ≈34 dk. Önkoşul Ders 30 (sirkülant/cyclic shift P/birim kökleri), Ders 3 (ortogonal Q) ve Ders 4 (köşegenleştirme/özvektör matrisi).

30.1 Bu Derste Ne Var?

Bu ders Fourier matrisi F’yi beş adımda inşa eder: Toeplitz ile sirkülantı ayır, ailenin ortak adı olan normal matrisi tanımla, özvektörleri w kuvvetlerine indirge, F’yi kur ve sonunda her sirkülantı F’de köşegenleştir.

Beş sonuç:

Toeplitz vs sirkülant: sabit-köşegen Toeplitz = (döngüsüz) evrişim; sirkülant = döngüsel evrişim. ML matrisleri böyle özeldir (ağırlık paylaşımı).
Normal matris: $M^{*}M = MM^{*}$; ortogonal özvektörlü matrisler (simetrik, diyagonal, ortogonal, antisimetrik, sirkülant). Sirkülantlar değişmeli → normal.
Özvektörler = w kuvvetleri: $w = e^{2\pi i/n}$ (birim kökü); P’nin (ve tüm sirkülantların) özvektörleri.
Fourier matrisi: F = özvektör matrisi; $F_{jk} = w^{jk}$; kolonlar ortogonal (uzunluk $\sqrt{n}$), $F/\sqrt{n}$ ortonormal.
Sonuç: her sirkülant F’de köşegenleşir ($C = F\Lambda F^{-1}$); evrişim çarpmaya döner; FFT $O(n \log n)$.

“…Fourier matrix equals eigenvector matrix.” — Strang, 43:39

flowchart TD
    C["Fourier matrisi F =<br/>tum sirkulantlarin ozvektor matrisi"]

    C --> E["Toeplitz dongusuz /<br/>sirkulant dongusel evrisim"]
    C --> N["normal matris: M*M = MM*<br/>(ortogonal ozvektor ailesi)"]
    C --> W["ozvektorler = w kuvvetleri,<br/>w = e^(2 pi i / n)"]
    C --> J["F_jk = w^(jk);<br/>kolonlar ortogonal sqrt(n)"]
    C --> D["C = F Lambda F^-1 -><br/>evrisim = carpma -> FFT O(n log n)"]

    K1["D30 sirkulant / birim kokleri"]
    K2["D3 ortogonal Q + D4 kosegenlestirme"]
    K3["D32 CNN (sonraki)"]
    K4["fast.ai L15 / NYU H6"]

    K1 --> C
    K2 --> N
    E --> K3
    D --> 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 E,N,W,J,D dal;
    class K1,K2 vec;
    class K3,K4 teal;

Şekil 30.1: Ders 31 kavram haritasi: Fourier matrisi F = tum sirkulantlarin ortak ozvektor matrisi. Bes dal: Toeplitz dongusuz evrisim (ML/CNN) vs sirkulant dongusel evrisim (DFT), fark yalniz sarmalamada; normal matris testi MM = MM -> ortogonal ozvektor ailesi (sirkulantlar uye); ozvektorler = w kuvvetleri, w = e^(2 pi i / n); F_jk = w^(jk), kolonlar ortogonal uzunluk sqrt(n); C = F Lambda F^-1 -> evrisim frekansta carpmaya doner -> FFT O(n log n). Koprular: D30 sirkulant/birim kokleri, D3 ortogonal Q + D4 kosegenlestirme, D32 CNN (sonraki), fast.ai L15 / NYU H6.

Şekil 30.1 dersin iskeletini gösterir: merkezdeki Fourier matrisi F = tüm sirkülantların ortak özvektör matrisi fikrinden beş dala ayrılır — Toeplitz döngüsüz / sirkülant döngüsel evrişim, normal matris testi $M^{*}M = MM^{*}$ (ortogonal özvektör ailesi), özvektörler = w kuvvetleri ($w = e^{2\pi i/n}$), $F_{jk} = w^{jk}$ kolonlar ortogonal uzunluk $\sqrt{n}$, ve $C = F\Lambda F^{-1}$ → evrişim frekansta çarpmaya döner → FFT $O(n \log n)$; köprü düğümleri D30 (sirkülant/birim kökleri), D3 ortogonal Q + D4 köşegenleştirme, D32 CNN (sonraki) ve fast.ai L15 / NYU H6 dalları önceki ve sonraki derslere bağlar.

Builder Notu — Dünyanın En Önemli Kompleks Matrisi

Fourier matrisi = dünyanın en önemli kompleks matrisi (Strang); tüm sirkülantlar onda köşegenleşir → evrişim teoremi → FFT.
ML görüntü: milyon-piksel feature; tam 3M×3M ağırlık imkansız → konvolüsyon (Toeplitz, ağırlık paylaşımı) + max pooling. CNN’in (Ders 32) temeli.
Normal matris — ortogonal özvektörlü tüm ailenin adı; $M^{*}M=MM^{*}$ testi (Ders 3 ortogonal, Ders 4 özvektör matrisi).
Geriye köprü: Ders 30 (sirkülant/P/birim kökleri), Ders 3 (ortogonal Q), Ders 4 (özvektör matrisi/köşegenleştirme), Ders 32 (CNN — sonraki). Paralel: fast.ai L15 (conv), NYU H6 (CNN).

Tek cümle: Tüm sirkülant matrisler aynı özvektör matrisini — Fourier matrisi F’yi ($F_{jk}=w^{jk}$, $w=e^{2\pi i/n}$) — paylaşır; bu matris tüm sirkülantları köşegenleştirir, evrişimi çarpmaya çevirir ve FFT’yi ($O(n \log n)$) mümkün kılar.

30.2 1. Toeplitz vs Sirkülant: Konvolüsyon

Sirkülantlar ayrık Fourier dönüşümüyle (DFT) yakından bağlı:

“…the discrete Fourier transform is… a very, very important algorithm in engineering…” — Strang, 2:49

Sirkülant n×n matris sadece n sayıyla (ilk satır) tanımlanır, n² değil. Genel hâli: sabit-köşegenli ama döngüsüz matris. Adı:

“…math people would call it a Toeplitz matrix.” — Strang, 9:16

\[\text{Toeplitz } T: \text{ sabit kosegen, dongusuz} \;\Rightarrow\; Tv = \text{(dongusuz) evrisim}\]

Sirkülant C ile çarpmak döngüsel (cyclic) evrişim; Toeplitz T ile çarpmak döngüsüz evrişim. İkisi de “linear shift/time invariant” (LSI/LTI) — sinyal işlemede filtre, evrişim. ML’de genelde Toeplitz (döngüsüz konvolüsyon) çıkar.

Kod

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

# Sol: Toeplitz (alt-üçgen, döngüsüz)
T5 = toeplitz_lower([3, 1, 2], 5)
heatmap(axes[0], T5, title="Toeplitz: sabit kosegen, DONGUSUZ", fmt="{:.0f}")

# Orta: sirkülant (köşeler sarar)
C5 = np.asarray(circulant([3, 1, 2, 0, 0]), float)
heatmap(axes[1], C5, title="sirkulant: koseler SARAR", fmt="{:.0f}")

# Sağ: T@v vs C@v bar karşılaştırma
v = np.array([4., 6, 1])
T = toeplitz_lower([3, 1, 2], 3)
C = circulant([3., 1, 2])
Tv = T @ v          # (12, 22, 17)
Cv = np.asarray(C @ v, float)   # (25, 24, 17)
x = np.arange(3)
ax = axes[2]
b1 = ax.bar(x - 0.18, Tv, width=0.36, color=COL_PRIMARY, label="T·v (döngüsüz)")
b2 = ax.bar(x + 0.18, Cv, width=0.36, color=COL_VEC3, label="C·v (döngüsel)")
for rects in (b1, b2):
    for r in rects:
        ax.text(r.get_x() + r.get_width()/2, r.get_height() + 0.4,
                f"{r.get_height():.0f}", ha="center", va="bottom",
                color=COL_TEXT, fontsize=9, fontweight="bold")
ax.set_xticks(x); ax.set_xticklabels(["1", "2", "3"])
ax.set_title("T·v vs C·v", color=COL_TEXT, fontsize=12, fontweight="bold")
ax.set_ylim(0, max(Cv) * 1.25)
ax.annotate("fark (13,2,0) = sarmalama (D30 tasan terimleri)",
            xy=(0, Cv[0]), xytext=(0.05, max(Cv) * 1.12),
            fontsize=8.5, color=COL_VEC3, fontweight="bold")
ax.legend(loc="upper right", fontsize=8)
apply_style(ax)

fig.suptitle("Iki lehce: Toeplitz dongusuz evrisim (ML/CNN), sirkulant dongusel evrisim (DFT) — fark yalniz sarmalamada",
             color=COL_TEXT, fontsize=11, fontweight="bold", y=1.02)
fig.tight_layout()
plt.show()

Şekil 30.2: İki lehçe: Toeplitz döngüsüz evrişim (ML/CNN), sirkülant döngüsel evrişim (DFT) — fark yalnız sarmalamada. Sol Toeplitz alt-üçgen sabit köşegen; orta sirkülant köşeler sarar; sağ T·v=(12,22,17) ile C·v=(25,24,17), fark (13,2,0) = D30’un taşan terimleri.

Şekil 30.2 iki lehçeyi yan yana koyar: solda Toeplitz alt-üçgen (sabit köşegen, döngüsüz), ortada sirkülant (köşeleri saran), sağda aynı $v$ üzerine her ikisinin etkisi. Toeplitz çarpımı $T\cdot v = (12, 22, 17)$ döngüsüzdür (linear_conv’un ilk üç terimi); sirkülant çarpımı $C\cdot v = (25, 24, 17)$ döngüseldir. Fark $C\cdot v - T\cdot v = (13, 2, 0)$ tam olarak sarmalama (wrap-around) terimleridir — Ders 30’un döngüsel evrişimde başa sardığını gördüğümüz taşan 13 ve 2’sidir. İki dünya yalnızca bu sarmalamada ayrılır.

Builder Notu — Evrişimin İki Lehçesi

“Sirkülant = döngüsel evrişim, Toeplitz = döngüsüz evrişim” sinyal işlemenin matris dili. ML köprüsü: CNN’in konvolüsyon katmanı bir Toeplitz operasyonudur — aynı filtre tüm konumlara kaydırarak uygulanır (ağırlık paylaşımı). fast.ai L15 im2col bu Toeplitz yapısını matris çarpımına açar.

30.3 2. ML Görüntü: Neden Özel Matrisler?

Sirkülant/Toeplitz neden ML’de kritik? Görüntü = piksel; 1000×1000 görüntü = bir milyon özellik (renkte 3 milyon). Sıradan tam matrisle:

\[\text{tam matris: } 3\text{M} \times 3\text{M} \text{ agirlik} \;\Rightarrow\; \text{imkansiz}\]

3M×3M ağırlığı her katmanda hesaplamak imkansız — gradient descent bu kadar ağırlığı optimize edemez. Çözüm: ML matrisleri özeldir (sirkülant/Toeplitz gibi) — aynı operasyon her noktada (ağırlık paylaşımı). Max pooling boyutu düşürür (9 pikseli 1’e indir, maksimumu al — doğrusal değil ama hızlı); low-pass filtre yüksek frekansı (gürültüyü) kırar (örn. [½, ½] komşu ortalama).

Kod

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))

# Sol: ML ölçek — tam matris vs konvolüsyon filtre (log-ölçek)
vals = [9e12, 9]
cols = [COL_VEC3, COL_PRIMARY]
bars = ax1.bar(["3Mx3M tam matris", "3x3 conv filtre"], vals, color=cols, width=0.6)
ax1.set_yscale("log")
ax1.set_title("tam-bagli vs konvolusyon", color=COL_TEXT, fontsize=12, fontweight="bold")
ax1.set_ylabel("agirlik sayisi (log)")
labels = ["9 trilyon agirlik (imkansiz)", "9 agirlik (paylasimli)"]
for b, lab in zip(bars, labels):
    ax1.annotate(lab, (b.get_x() + b.get_width()/2, b.get_height()),
                 ha="center", va="bottom", fontsize=9, fontweight="bold", color=COL_TEXT)
ax1.set_ylim(1, 1e14)
apply_style(ax1)

# Sağ: low-pass [1/2,1/2] demo
t, noisy, smooth, clean = low_pass_demo()
ax2.plot(t, noisy, color=COL_STEEL_300, lw=1, label="gurultulu")
ax2.plot(t, smooth, color=COL_PRIMARY, lw=2, label="low-pass [1/2,1/2]")
ax2.set_title("MSE 0.0945 -> 0.0571", color=COL_TEXT, fontsize=12, fontweight="bold")
ax2.set_xlabel("t")
ax2.legend(loc="upper right", framealpha=0.9)
apply_style(ax2)

fig.suptitle("ML matrisleri OZEL olmak zorunda: agirlik paylasimi (Toeplitz) + pooling + low-pass — 3Mx3M tam matris gradient descent icin imkansiz",
             fontsize=10, color=COL_TEXT, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 30.3: ML matrisleri özel olmak zorunda: 3M×3M tam-bağlı matris 9 trilyon ağırlık (imkânsız) iken 3×3 konvolüsyon filtresi yalnız 9 paylaşımlı ağırlık; low-pass [1/2, 1/2] gürültüyü yumuşatır (MSE 0.0945 → 0.0571).

Şekil 30.3 ölçek sorununu somutlaştırır: solda 3M×3M tam-bağlı matris 9 trilyon ağırlık (imkansız) iken 3×3 konvolüsyon filtresi yalnızca 9 paylaşımlı ağırlık taşır (log-ölçek bu uçurumu sığdırır); sağda [½, ½] komşu-ortalama low-pass filtresi gürültülü sinyali yumuşatır — gürültü MSE’si 0.0945 → 0.0571 düşer (motor-tanıklı iyileşme). İkisi birlikte ML’in ölçeklenme sırrını gösterir: ağırlık paylaşımı (Toeplitz) parametre sayısını trilyonlardan binlere indirir, pooling boyutu azaltır, low-pass gürültü giderir.

Builder Notu — Üç Milyona Üç Milyon İmkansızı

“3M×3M imkansız → konvolüsyon + pooling” derin öğrenmenin ölçeklenme sırrı. ML köprüsü: tam-bağlı (fully-connected) katman milyar parametre olurdu; konvolüsyon ağırlık paylaşımıyla bunu binlere indirir (CNN’in zaferi, Ders 32). Max pooling boyut azaltır, low-pass filtre gürültü giderir — ikisi de görüntü işlemenin standart adımları.

30.4 3. Normal Matris: Ortogonal Özvektörlü Aile

Ortogonal özvektörlere sahip matrislerin tüm ailesinin adı:

“…a matrix of that form is a normal matrix.” — Strang, 32:20

Normal matris: $M = Q\Lambda Q^{*}$ (ortogonal/üniter özvektörler Q, herhangi karmaşık özdeğerler Λ). Test: M, eşlenik-transpozuyla değişmeli (commute):

\[M^{*}M = MM^{*} \quad (\text{normal matris testi})\]

Bu aile simetrik ($A^{\top}=A$), diyagonal, ortogonal (real λ veya |λ|=1), antisimetrik (sanal λ) ve sirkülant matrisleri kapsar. Sirkülantlar neden normal? Çünkü değişmelidirler:

“…circulant matrices commute. Any 2 circulant matrices commute.” — Strang, 36:06

İki sirkülant $C_1 C_2 = C_2 C_1$ (ikisi de P’nin polinomu, polinomlar değişmeli). Dolayısıyla C ortogonal özvektörlere sahip — ayrıca hesaplamadan biliyoruz.

Kod

fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(10.5, 4.2))

# Sol: 6 uye normality_defect bar (log olcek)
fam = normal_family(seed=31)
names = list(fam.keys())
defects = [max(normality_defect(M), 1e-17) for M in fam.values()]
colors = [COL_PRIMARY] * len(names)
# Jordan (degil) = turuncu
for i, nm in enumerate(names):
    if "jordan" in nm.lower():
        colors[i] = COL_VEC3
ax0.bar(range(len(names)), defects, color=colors)
ax0.set_yscale("log")
ax0.set_xticks(range(len(names)))
ax0.set_xticklabels(names, rotation=20, ha="right")
ax0.set_title("M*M = MM* testi: 5 uye SIFIR, Jordan = 1", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(ax0)

# Sag: sirkulantlar degismeli heatmap |C1C2 - C2C1| = 0
rng = np.random.default_rng(7)
C1 = circulant(rng.uniform(-2, 2, 4))
C2 = circulant(rng.uniform(-2, 2, 4))
comm = np.abs(C1 @ C2 - C2 @ C1)
heatmap(ax1, comm, title="sirkulantlar degismeli: |C1C2 - C2C1| = 0", fmt="{:.0f}")

fig.suptitle("Normal matris ailesi: ortogonal ozvektorun soyadi — sirkulantlar degismeli oldugu icin uyedir (hesapsiz kanit)", color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 30.4: Normal matris ailesi: MM = MM testi 5 üyede SIFIR (defect ≤ 4.44e-16), Jordan bloğunda 1.0 — sirkülantlar değişmeli olduğu için ailenin üyesidir (hesapsız kanıt).

Şekil 30.4 aileyi ve değişmeliliği bir arada doğrular: solda altı üyenin $M^{*}M = MM^{*}$ defect’i — simetrik, diyagonal, ortogonal, antisimetrik ve sirkülant beşi sıfırda (defect ≤ 4.44e-16, log-ölçek tabanında), Jordan bloğu [[1,1],[0,1]] ise 1.0 ile turuncu olarak ayrışır (normal değil — kontrast). Sağda iki rastgele sirkülantın değişmeliliği: $|C_1 C_2 - C_2 C_1|$ tam sıfır matristir (motorda $C_1 C_2 - C_2 C_1 < 1\text{e-}12$). İki sirkülant her zaman değişmeli olduğundan, sirkülantlar normaldir — ortogonal özvektörlere hesaplamadan sahip olduklarını biliriz.

Builder Notu — Ortogonal Özvektörlülerin Soyadı

“Normal matris = ortogonal özvektörlü aile, MM=MM” spektral teoremin (Ders 4) en geniş hâli: simetrik-ötesi, karmaşık özdeğerli ama hâlâ ortogonal özvektörlü. ML köprüsü: normal matrisler güvenli köşegenleştirme verir (kararlı, ortonormal taban); sirkülantların normal olması, Fourier tabanının (özvektörler) ortogonal olmasını garantiler — sinyal işlemenin sağlamlığı buradan.

30.5 4. Özvektörler = w Kuvvetleri

C = P’nin polinomu olduğundan, C’nin özvektörleri = P’nin özvektörleri (Ders 30). P’nin özvektörleri çok özel — Fourier bağlantısı (çünkü periyodik):

“…everything is going to be powers of w. e to the 2 pi i over N…” — Strang, 41:59

\[w = e^{2\pi i/n} \quad (\text{birim cemberin 1/n'i})\]

w, n’inci birim köküdür (karmaşık düzlemde dairenin 1/n’i kadar). λ=1 özvektörü (1,1,1,1); λ=−1 için (1,−1,1,−1); λ=i için (1, i, i², i³); λ=−i için (1, −i, (−i)², (−i)³). Her özvektörün bileşenleri w’nin kuvvetleri. P’yi (kaydırma) bir özvektörle çarpmak, onu w (veya bir kuvveti) ile ölçekler.

Kod

fig, axes = plt.subplots(1, 2, figsize=(10.5, 4.4))

# --- Sol: n=8 birim çember + w kuvvetleri ---
ax = axes[0]
theta = np.linspace(0, 2*np.pi, 400)
ax.plot(np.cos(theta), np.sin(theta), color=COL_STEEL_300, linewidth=1.0)
n = 8
w = np.exp(2j * np.pi / 8)
powers = w ** np.arange(n)
ax.scatter(powers.real, powers.imag, s=100, color=COL_PRIMARY, zorder=5)
for kk in range(n):
    p = powers[kk]
    ax.annotate(f"w^{kk}", (p.real, p.imag),
                textcoords="offset points", xytext=(8, 8),
                color=COL_TEXT, fontsize=10, fontweight="bold")
ax.annotate("", xy=(powers[1].real, powers[1].imag), xytext=(0, 0),
            arrowprops=dict(arrowstyle="->", color=COL_VEC3, linewidth=2.2))
ax.set_title("w = e^(2 pi i/8): 8 birim koku", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(ax)
ax.set_aspect("equal")

# --- Sağ: F8 kolonlarının reel kısmı = frekans dalgaları ---
ax = axes[1]
F8 = fourier_matrix(8)
col_colors = [COL_ACCENT, COL_PRIMARY, COL_VEC3, COL_TEAL]
for k in range(4):
    ax.plot(range(8), F8[:, k].real, marker="o", color=col_colors[k], label=f"k={k}")
ax.legend()
ax.set_title("F kolonlari = frekans dalgalari (Re kismi)", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(ax)

fig.suptitle(
    "Ozvektorler w kuvvetleri: her kolon farkli frekansta kompleks ustel dalga — "
    "sinyali bunlara ayirmak = Fourier analizi",
    color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.92])
plt.show()

Şekil 30.5: Özvektörler w kuvvetleri: her kolon farklı frekansta kompleks üstel dalga — sinyali bunlara ayırmak = Fourier analizi. Solda n=8 birim çemberinde w = e^(2 pi i/8) kuvvetleri w^0..w7; sağda F8 kolonlarının reel kısmı k=0..3 frekans dalgaları.

Şekil 30.5 özvektörlerin geometrisini açar: solda $w = e^{2\pi i/8}$’in sekiz kuvveti $w^0, \dots, w^7$ birim çember üzerinde eşit aralıklı sekiz noktadır (her biri $|\cdot|=1$), $w^1$ turuncu okla vurgulanır — kaydırma P’nin özdeğer kümesi. Sağda F8 kolonlarının reel kısmı: k=0 sabit (DC bileşeni), k=1, 2, 3 giderek artan frekansta kosinüs dalgaları. Her kolon farklı frekansta bir kompleks üstel dalgadır; bir sinyali bu kolonlara ayırmak tam olarak Fourier analizidir.

Builder Notu — Periyodiklik Fourier Doğurur

“Özvektörler = w kuvvetleri, w = e^{2πi/n}” periyodikliğin Fourier’e dönüştüğü an. ML köprüsü: bu birim-kök özvektörleri sinüs/kosinüs dalgalarıdır (karmaşık üstel = frekans bileşenleri); bir sinyali bu özvektörlere ayırmak = Fourier analizi; CNN’lerin frekans-uzayı yorumu ve spektral filtreleme buradan.

30.6 5. Fourier Matrisi F

Tüm özvektörleri kolon kolon dizince Fourier matrisi F çıkar — ve bu, tüm sirkülantların özvektör matrisidir:

“…Fourier matrix equals eigenvector matrix.” — Strang, 43:39

\[F_{jk} = w^{jk}, \qquad w = e^{2\pi i/n}\]

(j, k = 0, 1, …, n−1; her girdi w’nin bir kuvveti, satır×sütun indisi.) İlk kolon hep 1; sonraki kolonlar w’nin artan kuvvetleri.

“…the most important complex matrix in the world…” — Strang, 44:06

F’nin kolonları ortogonaldir (uzunluk $\sqrt{n}$); $F/\sqrt{n}$ ortonormaldir (normal matrisin ortogonal özvektörleri, §3). n=8 için son kolon $w^0, w^7, w^{14}, \dots, w^{49}$ ($w^{48}=1$ olduğundan $w^{49}=w$).

Kod

fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(11, 4.6))

# Sol: F8 FAZ CARKI
F8 = fourier_matrix(8)
n = 8
# steel ince grid (hucre sinirlari)
for x in range(n + 1):
    ax0.axvline(x - 0.5, color=COL_STEEL_300, linewidth=0.6, alpha=0.7)
    ax0.axhline(x - 0.5, color=COL_STEEL_300, linewidth=0.6, alpha=0.7)
for j in range(n):
    for k in range(n):
        arg = np.angle(F8[j, k])
        cx, cy = k, 7 - j  # merkez (k, 7-j)
        dx = 0.35 * np.cos(arg); dy = 0.35 * np.sin(arg)
        ax0.annotate("", xy=(cx + dx, cy + dy), xytext=(cx - dx, cy - dy),
                     arrowprops=dict(arrowstyle="->", color=COL_PRIMARY, lw=1.3))
ax0.set_xlim(-0.7, 7.7); ax0.set_ylim(-0.7, 7.7)
ax0.set_aspect("equal")
ax0.set_title("F8: her girdi w^(jk) — saat yonu faz carki", color=COL_TEXT, fontsize=12, fontweight="bold")
ax0.axis("off")
ax0.annotate("F[7,7] = w^49 = w", xy=(7, 0), xytext=(3.0, -0.5),
             color=COL_VEC3, fontsize=10, fontweight="bold",
             arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.2))

# Sag: |F^H F| heatmap
FHF = np.abs(F8.conj().T @ F8)
heatmap(ax1, FHF, title="F^H F = 8I: kolonlar ortogonal (defect 4.3e-14)", fmt="{:.0f}", fontsize=10)

fig.suptitle("Dunyanin en onemli kompleks matrisi: F_jk = w^jk, kolonlar ortogonal uzunluk sqrt(8) — F/sqrt(n) uniter", color=COL_TEXT, fontsize=11, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.93])
plt.show()

Şekil 30.6: Dünyanın en önemli kompleks matrisi F8: her girdi F_jk = w^jk bir faz çarkı (sol), kolonlar ortogonal — F^H F = 8I (sağ, defect 4.3e-14), uzunluk √8, F/√n üniter.

Şekil 30.6 dersin amiral görselidir: solda F8’in her girdisi $F_{jk} = w^{jk}$ bir faz oku olarak çizilir — saat yönünde ilerleyen bir faz çarkı; köşe girdisi $F[7,7] = w^{49} = w$ ($w^{48}=1$ olduğundan, Notion örneğinin motor-teyitli sonucu) turuncu okla işaretlenir. Sağda $|F^{H}F|$ ısı haritası tam $8I$’dır: köşegende 8, köşegen-dışında 0 — kolonlar ortogonaldir, ortogonallik defect’i n=8 için yalnızca 4.3e-14 (n=2 için 1.2e-16, n=4 için 4.7e-16). Kolonların uzunluğu $\sqrt{8}$, dolayısıyla $F/\sqrt{n}$ üniterdir.

Builder Notu — Bütün Frekanslar Tek Matriste

“F = özvektör matrisi, $F_{jk}=w^{jk}$” sinyal işlemenin merkez nesnesi. ML köprüsü: F bir sinyali frekans bileşenlerine ayırır (DFT); kolonları farklı frekanslardaki karmaşık üstel dalgalar. Görüntü/ses sıkıştırma (JPEG/MP3), spektral filtreleme ve CNN’lerin Fourier-uzayı analizi hep F’ye dayanır.

30.7 6. Köşegenleştirme ve FFT

Tüm sirkülantlar aynı F’de köşegenleşir:

\[C = F\,\Lambda\,F^{-1}, \qquad \Lambda = \text{diag(c'nin Fourier donusumu)}\]

Özdeğerler Λ, ilk kolonun (c) Fourier dönüşümüdür (Fc). İşte konvolüsyon teoremi: C ile çarpmak (zaman uzayında evrişim) = F ile frekans uzayına git, Λ ile çarp (frekansta çarpma), F⁻¹ ile geri dön. Evrişim → çarpma. Ve FFT (hızlı Fourier dönüşümü), F·v çarpımını saf O(n²) yerine O(n log n)’de yapar — w kuvvetlerinin özyinelemeli yapısını kullanarak.

Kod

fig, axes = plt.subplots(1, 3, figsize=(12, 4))
c4 = np.random.default_rng(31).uniform(-2, 2, 4)
d4 = np.array([4., 6, 1, 2])

# Sol: C = F Lambda F^-1 rekonstrüksiyon
defect, lam = circulant_reconstruct_defect(c4)
heatmap(axes[0], np.asarray(circulant(c4), float),
        title="C = F Lambda F^-1 (rekonstruksiyon 7.6e-16)", fmt="{:.2f}")

# Orta: konvolüsyon teoremi — evrişim frekansta çarpmaya döner
lhs = np.abs(np.fft.fft(cyclic_conv(c4, d4)))
rhs = np.abs(np.fft.fft(c4) * np.fft.fft(d4))
x = np.arange(4)
axes[1].bar(x - 0.18, lhs, width=0.36, color=COL_PRIMARY, label="FFT(c conv d)")
axes[1].bar(x + 0.18, rhs, width=0.36, color=COL_VEC3, label="FFT(c) * FFT(d)")
axes[1].set_title("evrisim = frekansta carpma (defect 0.0)", color=COL_TEXT, fontsize=12, fontweight="bold")
axes[1].set_xticks(x); axes[1].set_xlabel("frekans indeksi k")
axes[1].set_ylabel("genlik |.|"); axes[1].legend(fontsize=9)
apply_style(axes[1])

# Sağ: FFT n log n vs DFT n² ölçek
ns = 2**np.arange(4, 15)
axes[2].loglog(ns, ns * np.log2(ns), color=COL_PRIMARY, marker="o", label="FFT n log n")
axes[2].loglog(ns, ns**2.0, color=COL_VEC3, marker="s", label="DFT n^2")
axes[2].axvline(1024, color=COL_STEEL_300, linestyle="--", linewidth=1.2)
axes[2].annotate("n=1024: 102x", xy=(1024, 1024 * np.log2(1024)),
                 xytext=(60, 4e6), fontsize=9, color=COL_TEXT)
axes[2].annotate("n=4096: 341x", xy=(4096, 4096 * np.log2(4096)),
                 xytext=(400, 6e7), fontsize=9, color=COL_TEXT)
axes[2].set_title("FFT vs DFT olcek", color=COL_TEXT, fontsize=12, fontweight="bold")
axes[2].set_xlabel("boyut n"); axes[2].set_ylabel("islem sayisi"); axes[2].legend(fontsize=9)
apply_style(axes[2])

fig.suptitle("Uc zafer tek satirda: C = F Lambda F^-1, evrisim carpmaya doner (defect TAM 0.0), FFT n log n — n=1024 te 102x",
             color=COL_TEXT, fontsize=12, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()

Şekil 30.7: Üç zafer tek satırda: $C = F\Lambda F^{-1}$, evrişim çarpmaya döner (defect TAM 0.0), FFT $n\log n$ — $n=1024$’te 102×. Sol C = F Lambda F^-1 rekonstrüksiyon defect’i 7.6e-16; orta FFT(c⊛d) ile FFT(c)·FFT(d) barları üst üste (defect 0.0); sağ FFT n log n vs DFT n² log-log, n=1024’te 102×, n=4096’da 341×.

Şekil 30.7 dersin üç zaferini tek figürde toplar: solda rastgele bir sirkülant C’nin $F\Lambda F^{-1}$ rekonstrüksiyonu — fark 7.6e-16 (köşegenleştirme kimliği tam), özdeğerler $\lambda = \text{np.fft.fft}(c)$ birebir (Ders 30’un köşegen=FFT(c) köprü-sayısının devamı). Ortada konvolüsyon teoremi: $|FFT(c \circledast d)|$ ile $|FFT(c) \cdot FFT(d)|$ barları üst üste oturur — evrişim frekansta çarpmaya döner, defect tam 0.0 (n=4). Sağda FFT $n \log n$ ile DFT $n^2$ log-log eğrileri; n=1024’te oran 102× (FFT 10.240 vs DFT 1.048.576), n=4096’da 341× — n büyüdükçe açılan kazanç.

motor notu — w-yön konvansiyonu ve numpy DFT köprüsü

Strang tahtada $\Lambda = Fc$ der; bizim motor kurulumumuzda (ilk-kolon c, aşağı-kaydırma P) özdeğerler $\lambda = \text{np.fft.fft}(c) = \sum_m c_m \, w^{-mk}$ olarak çıkar. Motor circulant_reconstruct_defect tam bunu döndürür: $\lambda = \text{np.fft.fft}(c)$. Gerçek c’de Strang’ın $Fc$’si ile numpy’ın fft(c)’si eşlenik kümedir (Fc = conj(fft(c))) — büyüklükler $|\lambda|$ aynı, yalnız w-yönü konvansiyonu (saat-yönü) farklı. İkinci tanık: numpy DFT köprüsü $\text{np.fft.fft}(v) = \text{conj}(F)\cdot v$ ($w^{-jk}$ konvansiyonu). Pedagojik öz değişmez — Notion’ın cümlesine sadık kalırız, [motor notu] yalnızca konvansiyon dalını kaydeder.

Builder Notu — Üç Zafer Tek Satırda

“C = FΛF⁻¹, evrişim → çarpma, FFT O(n log n)” sinyal işlemenin üç zaferi tek satırda. ML köprüsü: büyük-çekirdek konvolüsyonlar FFT ile hızlandırılır (FFT-conv); ses modelleri (spektrogram), görüntü filtreleme ve bazı Transformer varyantları (FNet) Fourier dönüşümünü doğrudan kullanır. FFT, 20. yüzyılın en önemli algoritmalarından — sirkülant köşegenleştirmesinin meyvesi.

30.8 Bu Dersin Özeti

Toeplitz vs sirkülant: Toeplitz (sabit köşegen, döngüsüz) = evrişim; sirkülant = döngüsel evrişim. ML matrisleri böyle özel (ağırlık paylaşımı).
ML görüntü: milyon-piksel feature, 3M×3M tam matris imkansız → konvolüsyon + max pooling + low-pass filtre.
Normal matris: $M^{*}M = MM^{*}$; ortogonal özvektörlü aile (simetrik/diyagonal/ortogonal/antisimetrik/sirkülant). Sirkülantlar değişmeli → normal.
Özvektörler: $w = e^{2\pi i/n}$ kuvvetleri (birim kökleri); P’nin ve tüm sirkülantların özvektörleri.
Fourier matrisi: F = özvektör matrisi; $F_{jk} = w^{jk}$; kolonlar ortogonal (uzunluk $\sqrt{n}$), $F/\sqrt{n}$ ortonormal.
Köşegenleştirme/FFT: $C = F\Lambda F^{-1}$, $= $ c’nin DFT’si; evrişim → çarpma (konvolüsyon teoremi); FFT $O(n \log n)$.

Tek Bir Cümle

Tüm sirkülant matrisler aynı özvektör matrisini — Fourier matrisi F’yi ($F_{jk}=w^{jk}$, $w=e^{2\pi i/n}$) — paylaşır (çünkü normal ve değişmeli); bu matris her sirkülantı köşegenleştirir ($C=F\Lambda F^{-1}$), evrişimi çarpmaya çevirir (konvolüsyon teoremi) ve FFT’yi $O(n \log n)$ kılar.

30.9 Kontrol Soruları

Soru 1 — Toeplitz ve sirkülant farkı, ML’de hangisi çıkar

İkisi de sabit-köşegenli (linear shift invariant). Sirkülant döngüseldir (köşeleri sarar) → döngüsel evrişim; Toeplitz döngüsüzdür → (sıradan) evrişim. ML’de genelde Toeplitz çıkar: CNN’in konvolüsyon katmanı aynı filtreyi tüm konumlara kaydırarak uygular (ağırlık paylaşımı), döngüsel değil.

Soru 2 — Normal matris nedir, sirkülantlar neden normaldir

Normal matris ortogonal/üniter özvektörlere sahiptir; test: $M^{*}M = MM^{*}$ (eşlenik-transpozuyla değişmeli). Simetrik, diyagonal, ortogonal, antisimetrik ve sirkülant matrisleri kapsar. Sirkülantlar normaldir çünkü değişmelidirler ($C_1 C_2=C_2 C_1$, ikisi de P’nin polinomu); dolayısıyla ortogonal özvektörlere sahip olduklarını hesaplamadan biliriz.

Soru 3 — Fourier matrisi F’nin girdileri ve neden tüm sirkülantların özvektör matrisi

$F_{jk} = w^{jk}$, $w = e^{2\pi i/n}$ (n’inci birim kökü); her girdi w’nin satır×sütun kuvveti. Tüm sirkülantlar P’nin polinomu olduğundan hepsi P’nin özvektörlerini paylaşır; bu özvektörler w’nin kuvvetlerinden kurulu = F’nin kolonları. Kolonlar ortogonal (uzunluk $\sqrt{n}$); $F/\sqrt{n}$ üniter (normal matrisin ortogonal özvektörleri).

Soru 4 — C = FΛF⁻¹ neden evrişim = çarpma verir ve FFT’nin rolü

C ile çarpmak (zaman uzayında evrişim) = F ile frekans uzayına git, Λ (diagonal, c’nin Fourier dönüşümü) ile çarp, F⁻¹ ile dön. Diagonal çarpma basittir → evrişim frekansta çarpmaya döner (konvolüsyon teoremi). FFT, F·v çarpımını O(n²) yerine $O(n \log n)$’de yapar (w kuvvetlerinin özyinelemeli yapısı); böylece evrişim/filtreleme çok hızlanır.

30.10 Egzersizler

Birim kök. n = 4 için $w = e^{2\pi i/4} = i$. $w^0, w^1, w^2, w^3$’ü hesapla (1, i, −1, −i). Bunların birim çember üzerinde 4 nokta olduğunu doğrula. (Motor tanığı: $w=i$ kuvvetleri $(1, i, -1, -i)$ — hepsi $|\cdot|=1$.)
Fourier matrisi. n = 2 için F (2×2) yaz: $w = e^{2\pi i/2} = -1$. $F_{jk} = w^{jk}$ ile $F = [[1,1],[1,-1]]$ olduğunu göster. Kolonlar ortogonal mi? Uzunlukları $\sqrt{2}$ mi? (Motor tanığı: $F(n{=}2) = [[1,1],[1,-1]]$; kolonlar ortogonal, uzunluklar $\sqrt{2}$ — birebir.)
Normal test. Sirkülant $C = [[2,1],[1,2]]$ (simetrik). $C^{*}C = CC^{*}$ mı? (Simetrik olduğundan normal mi?) Antisimetrik $[[0,1],[-1,0]]$ normal mi (eşlenik-transpozla değişmeli mi)? (Motor tanığı: $C=[[2,1],[1,2]]$ defect 0 → normal; antisimetrik $[[0,1],[-1,0]]$ defect 0 → normal.)
Konvolüsyon teoremi. İki sirkülantın çarpımı = döngüsel evrişim (Ders 30). Bu Fourier’de neye karşılık gelir? (İpucu: $C = F\Lambda F^{-1}$, çarpım → Λ’ların çarpımı → frekansta nokta-çarpım.) (Motor tanığı: $FFT(c \circledast d) = FFT(c)\cdot FFT(d)$, defect tam 0.0 n=4’te ve <1e-10 n=3 Notion örneğinde.)
(Ders 32 habercisi) Fourier/sirkülant fikrini 2 boyuta (görüntü) taşı. Bir görüntüye uygulanan konvolüsyon nasıl çalışır? CNN’ler bunu nasıl katman katman kullanır? Bir tahmin yaz — Ders 32 “ImageNet bir CNN’dir, evrişim kuralı”nı işliyor.

30.11 Sonraki Ders İçin Hazırlık

Ders 32: ImageNet bir CNN’dir, Evrişim Kuralı. Sirkülant/Fourier fikri 2B görüntüye genişler: konvolüsyonel sinir ağları (CNN). Evrişim kuralı (kaydır-çarp-topla), filtre/çekirdek, ağırlık paylaşımı; ImageNet’in CNN devrimini başlatması. fast.ai L15 (conv2d/im2col) ve NYU H6 (CNN) ile birebir köprü.

Hazırlık

Bu dersin Egzersiz 5’inin sorduğu soruyu zihninde tut: bu derste 1B sinyale uyguladığımız sirkülant/Fourier fikrini 2B görüntüye nasıl taşırsın? Ders 32, konvolüsyonel sinir ağlarını (CNN) işler — aynı filtre tüm görüntü konumlarına kaydırılarak uygulanır (Toeplitz ağırlık paylaşımı), max pooling boyutu düşürür, ve ImageNet’in CNN devrimi başlar. fast.ai L15 (conv2d/im2col) ve NYU H6 (CNN) bu dersle birebir köprü kurar.

30.12 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
DFT	sirkülant ↔︎ ayrık Fourier dönüşümü	2m49
Toeplitz	sabit köşegen, döngüsüz = konvolüsyon	9m16
Normal matris	$M^{}M = MM^{}$; ortogonal özvektör	32m20
Sirkülantlar değişmeli	$C_1 C_2 = C_2 C_1$ → normal	36m06
Özvektörler = w kuvvetleri	$w = e^{2\pi i/n}$ (birim kökü)	41m59
Fourier matrisi	F = özvektör matrisi; $F_{jk} = w^{jk}$	43m39
Köşegenleştirme/FFT	$C = F\Lambda F^{-1}$; evrişim → çarpma; $O(n \log n)$	44m06

30.13 ML Bağlantıları Özeti

Fourier matrisi = en önemli kompleks matris: tüm sirkülantlar onda köşegenleşir → evrişim teoremi → FFT ($O(n \log n)$).
CNN = Toeplitz konvolüsyon: aynı filtre tüm konumlara (ağırlık paylaşımı); 3M×3M tam matris yerine küçük filtre; fast.ai L15 im2col/conv2d.
Max pooling + low-pass: boyut azaltma + gürültü giderme; görüntü işlemenin standart adımları.
FFT-conv: büyük-çekirdek konvolüsyon FFT ile hızlanır; ses (spektrogram), FNet (Fourier Transformer) doğrudan F kullanır.
Normal matris/spektral: ortogonal özvektörlü aile güvenli köşegenleştirme; graf sinyal işleme (spektral GCN, NYU paralel) Laplacian özvektörlerine genelleştirir.
Geriye köprü: Ders 30 (sirkülant/P/birim kökleri), Ders 3 (ortogonal Q), Ders 4 (özvektör matrisi/köşegenleştirme). Paralel: fast.ai L15 (convolution), NYU H6 (CNN).

Kapanış

“…the most important complex matrix in the world…” — Strang, 44:06

Fourier matrisi tüm sirkülantların ortak özvektör tabanıdır; bu tek matris evrişimi çarpmaya çevirir, FFT’yi mümkün kılar ve sinyal işleme ile CNN’lerin köprüsüdür.

--- title: "Sirkülant Matrislerin Özvektörleri — Fourier Matrisi" subtitle: "Toeplitz ve sirkülant evrişim, normal matris ailesi ve dünyanın en önemli kompleks matrisi" --- ::: {.callout-note title="Bölüm bilgisi"} Bu ders, Ders 30'un sirkülantlarının özvektörlerini somutlaştırır: **Fourier matrisi** F. Tüm sirkülantlar aynı özvektör matrisini paylaşır — bu, ayrık Fourier dönüşümü (DFT) ve FFT'nin temelidir. Strang'in [Ders 31 videosu](https://www.youtube.com/watch?v=1pFv7e9xtHo) (≈52 dk) ve [OCW Lecture 31](https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-31-eigenvectors-of-circulant-matrices-fourier-matrix/) temel alınmıştır. Okuma süresi ≈34 dk. Önkoşul Ders 30 (sirkülant/cyclic shift P/birim kökleri), Ders 3 (ortogonal Q) ve Ders 4 (köşegenleştirme/özvektör matrisi). ::: ```{python} #| echo: false """ _engine31.py — MIT 18.065 Ders 31 (Sirkülant Özvektörleri: Fourier Matrisi) motor + viz. Zincir: Toeplitz/sirkülant evrişim → normal matris ailesi (M*M=MM*) → w kuvvetleri → F_{jk}=w^{jk} ortogonal kolonlar → C=FΛF⁻¹ + konvolüsyon teoremi + FFT O(n log n). Setup hücresi = cat. Figür testi `from _engine31 import *`. matplotlib.use("Agg") burada YOK. """ import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import LinearSegmentedColormap 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 <= 64: 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") # ============ D30 TEMELİ (self-contained tekrar) ============ def cyclic_P(n=4): """Döngüsel kaydırma: (Px)_i = x_{(i-1) mod n} — bir aşağı, 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 + … (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): """Doğrusal (döngüsüz) evrişim — Toeplitz dünyası.""" return np.convolve(np.asarray(a, float), np.asarray(b, float)) def cyclic_conv(a, b): """Döngüsel evrişim — sirkülant dünyası (taşan terimler başa sarar).""" 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] = w^{jk}, w = e^{2πi/n} — tüm sirkülantların özvektör matrisi.""" w = np.exp(2j * np.pi / n) j, k = np.meshgrid(np.arange(n), np.arange(n), indexing="ij") return w ** (j * k) # ============ (1) TOEPLITZ vs SİRKÜLANT ============ def toeplitz_lower(c, n): """Causal (alt-üçgen) Toeplitz: T[i,j] = c[i−j] (i≥j) — döngüsüz filtre/evrişim matrisi.""" c = np.asarray(c, float) T = np.zeros((n, n)) for i in range(n): for j in range(n): if 0 <= i - j < len(c): T[i, j] = c[i - j] return T # ============ (3) NORMAL MATRİS AİLESİ ============ def normality_defect(M): """‖M*M − MM*‖_max — sıfır ⟺ normal (ortogonal özvektörlü).""" M = np.asarray(M, dtype=complex) return float(np.max(np.abs(M.conj().T @ M - M @ M.conj().T))) def normal_family(seed=31): """Ailenin beş üyesi + normal-OLMAYAN kontrast (Jordan bloğu).""" rng = np.random.default_rng(seed) A = rng.standard_normal((4, 4)) sym = (A + A.T) / 2 # simetrik diag = np.diag(rng.uniform(-2, 2, 4)) # diyagonal th = 0.7 rot = np.array([[np.cos(th), -np.sin(th)], [np.sin(th), np.cos(th)]]) # ortogonal anti = (A - A.T) / 2 # antisimetrik circ = circulant(rng.uniform(-2, 2, 4)) # sirkülant jordan = np.array([[1.0, 1.0], [0.0, 1.0]]) # normal DEĞİL return {"simetrik": sym, "diyagonal": diag, "ortogonal": rot, "antisimetrik": anti, "sirkulant": circ, "jordan (degil)": jordan} # ============ (5-6) FOURIER MATRİSİ + KÖŞEGENLEŞTİRME + FFT ============ def f_orthogonality_defect(n): """‖FᴴF − nI‖_max — sıfır ⟺ kolonlar ortogonal, uzunluk √n (F/√n üniter).""" F = fourier_matrix(n) return float(np.max(np.abs(F.conj().T @ F - n * np.eye(n)))) def circulant_reconstruct_defect(c): """‖C − F·diag(λ)·F⁻¹‖_max, λ = diag(F⁻¹CF) — köşegenleştirme kimliği.""" c = np.asarray(c, float); n = len(c) F = fourier_matrix(n); C = circulant(c) lam = np.diag(np.linalg.solve(F, C @ F)) Chat = F @ np.diag(lam) @ np.linalg.inv(F) return float(np.max(np.abs(C - Chat))), lam def conv_theorem_defect(c, d): """‖FFT(c ⊛ d) − FFT(c)·FFT(d)‖_max — konvolüsyon teoremi (evrişim → nokta-çarpım).""" lhs = np.fft.fft(cyclic_conv(c, d)) rhs = np.fft.fft(np.asarray(c, float)) * np.fft.fft(np.asarray(d, float)) return float(np.max(np.abs(lhs - rhs))) def fft_ops(n): """(yaklaşık işlem sayıları) FFT ~ n·log2(n) vs saf DFT ~ n² — O-karşılaştırması.""" return n * np.log2(n), float(n) ** 2 def low_pass_demo(n=120, seed=31): """[½, ½] komşu-ortalama low-pass: gürültülü sinyal → yumuşatılmış (fig-ml-olcek tanığı).""" rng = np.random.default_rng(seed) t = np.linspace(0, 4 * np.pi, n) clean = np.sin(t) + 0.4 * np.sin(3 * t) noisy = clean + rng.normal(0, 0.35, n) smooth = np.convolve(noisy, [0.5, 0.5], mode="same") return t, noisy, smooth, clean ``` ## Bu Derste Ne Var? {#sec-bu-derste-d31} Bu ders **Fourier matrisi** F'yi beş adımda inşa eder: Toeplitz ile sirkülantı ayır, ailenin ortak adı olan normal matrisi tanımla, özvektörleri w kuvvetlerine indirge, F'yi kur ve sonunda her sirkülantı F'de köşegenleştir. Beş sonuç: 1. **Toeplitz vs sirkülant:** sabit-köşegen Toeplitz = (döngüsüz) evrişim; sirkülant = döngüsel evrişim. ML matrisleri böyle özeldir (ağırlık paylaşımı). 2. **Normal matris:** $M^{*}M = MM^{*}$; ortogonal özvektörlü matrisler (simetrik, diyagonal, ortogonal, antisimetrik, sirkülant). Sirkülantlar **değişmeli** → normal. 3. **Özvektörler = w kuvvetleri:** $w = e^{2\pi i/n}$ (birim kökü); P'nin (ve tüm sirkülantların) özvektörleri. 4. **Fourier matrisi:** F = özvektör matrisi; $F_{jk} = w^{jk}$; kolonlar ortogonal (uzunluk $\sqrt{n}$), $F/\sqrt{n}$ ortonormal. 5. **Sonuç:** her sirkülant F'de köşegenleşir ($C = F\Lambda F^{-1}$); evrişim çarpmaya döner; FFT $O(n \log n)$. > *"...Fourier matrix equals eigenvector matrix." — Strang, 43:39* ```{mermaid} %%| label: fig-kavram-haritasi-l31 %%| fig-cap: "Ders 31 kavram haritasi: Fourier matrisi F = tum sirkulantlarin ortak ozvektor matrisi. Bes dal: Toeplitz dongusuz evrisim (ML/CNN) vs sirkulant dongusel evrisim (DFT), fark yalniz sarmalamada; normal matris testi M*M = MM* -> ortogonal ozvektor ailesi (sirkulantlar uye); ozvektorler = w kuvvetleri, w = e^(2 pi i / n); F_jk = w^(jk), kolonlar ortogonal uzunluk sqrt(n); C = F Lambda F^-1 -> evrisim frekansta carpmaya doner -> FFT O(n log n). Koprular: D30 sirkulant/birim kokleri, D3 ortogonal Q + D4 kosegenlestirme, D32 CNN (sonraki), fast.ai L15 / NYU H6." %%| echo: false flowchart TD C["Fourier matrisi F = tum sirkulantlarin ozvektor matrisi"] C --> E["Toeplitz dongusuz / sirkulant dongusel evrisim"] C --> N["normal matris: M*M = MM* (ortogonal ozvektor ailesi)"] C --> W["ozvektorler = w kuvvetleri, w = e^(2 pi i / n)"] C --> J["F_jk = w^(jk); kolonlar ortogonal sqrt(n)"] C --> D["C = F Lambda F^-1 -> evrisim = carpma -> FFT O(n log n)"] K1["D30 sirkulant / birim kokleri"] K2["D3 ortogonal Q + D4 kosegenlestirme"] K3["D32 CNN (sonraki)"] K4["fast.ai L15 / NYU H6"] K1 --> C K2 --> N E --> K3 D --> 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 E,N,W,J,D dal; class K1,K2 vec; class K3,K4 teal; ``` @fig-kavram-haritasi-l31 dersin iskeletini gösterir: merkezdeki **Fourier matrisi F = tüm sirkülantların ortak özvektör matrisi** fikrinden beş dala ayrılır — Toeplitz döngüsüz / sirkülant döngüsel evrişim, normal matris testi $M^{*}M = MM^{*}$ (ortogonal özvektör ailesi), özvektörler = w kuvvetleri ($w = e^{2\pi i/n}$), $F_{jk} = w^{jk}$ kolonlar ortogonal uzunluk $\sqrt{n}$, ve $C = F\Lambda F^{-1}$ → evrişim frekansta çarpmaya döner → FFT $O(n \log n)$; köprü düğümleri D30 (sirkülant/birim kökleri), D3 ortogonal Q + D4 köşegenleştirme, D32 CNN (sonraki) ve fast.ai L15 / NYU H6 dalları önceki ve sonraki derslere bağlar. ::: {.callout-tip title="Builder Notu — Dünyanın En Önemli Kompleks Matrisi"} - **Fourier matrisi = dünyanın en önemli kompleks matrisi** (Strang); tüm sirkülantlar onda köşegenleşir → evrişim teoremi → FFT. - **ML görüntü:** milyon-piksel feature; tam 3M×3M ağırlık imkansız → konvolüsyon (Toeplitz, ağırlık paylaşımı) + max pooling. CNN'in (Ders 32) temeli. - **Normal matris** — ortogonal özvektörlü tüm ailenin adı; $M^{*}M=MM^{*}$ testi (Ders 3 ortogonal, Ders 4 özvektör matrisi). - **Geriye köprü:** Ders 30 (sirkülant/P/birim kökleri), Ders 3 (ortogonal Q), Ders 4 (özvektör matrisi/köşegenleştirme), Ders 32 (CNN — sonraki). Paralel: fast.ai L15 (conv), NYU H6 (CNN). Tek cümle: Tüm sirkülant matrisler aynı özvektör matrisini — Fourier matrisi F'yi ($F_{jk}=w^{jk}$, $w=e^{2\pi i/n}$) — paylaşır; bu matris tüm sirkülantları köşegenleştirir, evrişimi çarpmaya çevirir ve FFT'yi ($O(n \log n)$) mümkün kılar. ::: ## 1. Toeplitz vs Sirkülant: Konvolüsyon {#sec-toeplitz-sirkulant} Sirkülantlar ayrık Fourier dönüşümüyle (DFT) yakından bağlı: > *"...the discrete Fourier transform is... a very, very important algorithm in engineering..." — Strang, 2:49* Sirkülant n×n matris sadece **n sayıyla** (ilk satır) tanımlanır, n² değil. Genel hâli: sabit-köşegenli ama **döngüsüz** matris. Adı: > *"...math people would call it a Toeplitz matrix." — Strang, 9:16* $$\text{Toeplitz } T: \text{ sabit kosegen, dongusuz} \;\Rightarrow\; Tv = \text{(dongusuz) evrisim}$$ Sirkülant C ile çarpmak **döngüsel** (cyclic) evrişim; Toeplitz T ile çarpmak **döngüsüz** evrişim. İkisi de "linear shift/time invariant" (LSI/LTI) — sinyal işlemede filtre, evrişim. ML'de genelde Toeplitz (döngüsüz konvolüsyon) çıkar. ```{python} #| label: fig-toeplitz-sirkulant #| fig-cap: "İki lehçe: Toeplitz döngüsüz evrişim (ML/CNN), sirkülant döngüsel evrişim (DFT) — fark yalnız sarmalamada. Sol Toeplitz alt-üçgen sabit köşegen; orta sirkülant köşeler sarar; sağ T·v=(12,22,17) ile C·v=(25,24,17), fark (13,2,0) = D30'un taşan terimleri." #| fig-width: 11.5 #| fig-height: 3.8 #| code-fold: true fig, axes = plt.subplots(1, 3, figsize=(11.5, 3.8)) # Sol: Toeplitz (alt-üçgen, döngüsüz) T5 = toeplitz_lower([3, 1, 2], 5) heatmap(axes[0], T5, title="Toeplitz: sabit kosegen, DONGUSUZ", fmt="{:.0f}") # Orta: sirkülant (köşeler sarar) C5 = np.asarray(circulant([3, 1, 2, 0, 0]), float) heatmap(axes[1], C5, title="sirkulant: koseler SARAR", fmt="{:.0f}") # Sağ: T@v vs C@v bar karşılaştırma v = np.array([4., 6, 1]) T = toeplitz_lower([3, 1, 2], 3) C = circulant([3., 1, 2]) Tv = T @ v # (12, 22, 17) Cv = np.asarray(C @ v, float) # (25, 24, 17) x = np.arange(3) ax = axes[2] b1 = ax.bar(x - 0.18, Tv, width=0.36, color=COL_PRIMARY, label="T·v (döngüsüz)") b2 = ax.bar(x + 0.18, Cv, width=0.36, color=COL_VEC3, label="C·v (döngüsel)") for rects in (b1, b2): for r in rects: ax.text(r.get_x() + r.get_width()/2, r.get_height() + 0.4, f"{r.get_height():.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=9, fontweight="bold") ax.set_xticks(x); ax.set_xticklabels(["1", "2", "3"]) ax.set_title("T·v vs C·v", color=COL_TEXT, fontsize=12, fontweight="bold") ax.set_ylim(0, max(Cv) * 1.25) ax.annotate("fark (13,2,0) = sarmalama (D30 tasan terimleri)", xy=(0, Cv[0]), xytext=(0.05, max(Cv) * 1.12), fontsize=8.5, color=COL_VEC3, fontweight="bold") ax.legend(loc="upper right", fontsize=8) apply_style(ax) fig.suptitle("Iki lehce: Toeplitz dongusuz evrisim (ML/CNN), sirkulant dongusel evrisim (DFT) — fark yalniz sarmalamada", color=COL_TEXT, fontsize=11, fontweight="bold", y=1.02) fig.tight_layout() plt.show() ``` @fig-toeplitz-sirkulant iki lehçeyi yan yana koyar: solda Toeplitz alt-üçgen (sabit köşegen, döngüsüz), ortada sirkülant (köşeleri saran), sağda aynı $v$ üzerine her ikisinin etkisi. Toeplitz çarpımı $T\cdot v = (12, 22, 17)$ döngüsüzdür (`linear_conv`'un ilk üç terimi); sirkülant çarpımı $C\cdot v = (25, 24, 17)$ döngüseldir. Fark **$C\cdot v - T\cdot v = (13, 2, 0)$** tam olarak sarmalama (wrap-around) terimleridir — Ders 30'un döngüsel evrişimde başa sardığını gördüğümüz taşan 13 ve 2'sidir. İki dünya yalnızca bu sarmalamada ayrılır. ::: {.callout-tip title="Builder Notu — Evrişimin İki Lehçesi"} "Sirkülant = döngüsel evrişim, Toeplitz = döngüsüz evrişim" sinyal işlemenin matris dili. ML köprüsü: CNN'in konvolüsyon katmanı bir Toeplitz operasyonudur — aynı filtre tüm konumlara kaydırarak uygulanır (ağırlık paylaşımı). fast.ai L15 im2col bu Toeplitz yapısını matris çarpımına açar. ::: ## 2. ML Görüntü: Neden Özel Matrisler? {#sec-ml-goruntu} Sirkülant/Toeplitz neden ML'de kritik? Görüntü = piksel; 1000×1000 görüntü = bir milyon özellik (renkte 3 milyon). Sıradan tam matrisle: $$\text{tam matris: } 3\text{M} \times 3\text{M} \text{ agirlik} \;\Rightarrow\; \text{imkansiz}$$ 3M×3M ağırlığı her katmanda hesaplamak imkansız — gradient descent bu kadar ağırlığı optimize edemez. Çözüm: ML matrisleri **özeldir** (sirkülant/Toeplitz gibi) — aynı operasyon her noktada (ağırlık paylaşımı). **Max pooling** boyutu düşürür (9 pikseli 1'e indir, maksimumu al — doğrusal değil ama hızlı); **low-pass filtre** yüksek frekansı (gürültüyü) kırar (örn. [½, ½] komşu ortalama). ```{python} #| label: fig-ml-olcek #| fig-cap: "ML matrisleri özel olmak zorunda: 3M×3M tam-bağlı matris 9 trilyon ağırlık (imkânsız) iken 3×3 konvolüsyon filtresi yalnız 9 paylaşımlı ağırlık; low-pass [1/2, 1/2] gürültüyü yumuşatır (MSE 0.0945 → 0.0571)." #| fig-width: 10 #| fig-height: 4 #| code-fold: true fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4)) # Sol: ML ölçek — tam matris vs konvolüsyon filtre (log-ölçek) vals = [9e12, 9] cols = [COL_VEC3, COL_PRIMARY] bars = ax1.bar(["3Mx3M tam matris", "3x3 conv filtre"], vals, color=cols, width=0.6) ax1.set_yscale("log") ax1.set_title("tam-bagli vs konvolusyon", color=COL_TEXT, fontsize=12, fontweight="bold") ax1.set_ylabel("agirlik sayisi (log)") labels = ["9 trilyon agirlik (imkansiz)", "9 agirlik (paylasimli)"] for b, lab in zip(bars, labels): ax1.annotate(lab, (b.get_x() + b.get_width()/2, b.get_height()), ha="center", va="bottom", fontsize=9, fontweight="bold", color=COL_TEXT) ax1.set_ylim(1, 1e14) apply_style(ax1) # Sağ: low-pass [1/2,1/2] demo t, noisy, smooth, clean = low_pass_demo() ax2.plot(t, noisy, color=COL_STEEL_300, lw=1, label="gurultulu") ax2.plot(t, smooth, color=COL_PRIMARY, lw=2, label="low-pass [1/2,1/2]") ax2.set_title("MSE 0.0945 -> 0.0571", color=COL_TEXT, fontsize=12, fontweight="bold") ax2.set_xlabel("t") ax2.legend(loc="upper right", framealpha=0.9) apply_style(ax2) fig.suptitle("ML matrisleri OZEL olmak zorunda: agirlik paylasimi (Toeplitz) + pooling + low-pass — 3Mx3M tam matris gradient descent icin imkansiz", fontsize=10, color=COL_TEXT, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` @fig-ml-olcek ölçek sorununu somutlaştırır: solda 3M×3M tam-bağlı matris **9 trilyon ağırlık** (imkansız) iken 3×3 konvolüsyon filtresi yalnızca **9 paylaşımlı ağırlık** taşır (log-ölçek bu uçurumu sığdırır); sağda [½, ½] komşu-ortalama low-pass filtresi gürültülü sinyali yumuşatır — gürültü MSE'si **0.0945 → 0.0571** düşer (motor-tanıklı iyileşme). İkisi birlikte ML'in ölçeklenme sırrını gösterir: ağırlık paylaşımı (Toeplitz) parametre sayısını trilyonlardan binlere indirir, pooling boyutu azaltır, low-pass gürültü giderir. ::: {.callout-tip title="Builder Notu — Üç Milyona Üç Milyon İmkansızı"} "3M×3M imkansız → konvolüsyon + pooling" derin öğrenmenin ölçeklenme sırrı. ML köprüsü: tam-bağlı (fully-connected) katman milyar parametre olurdu; konvolüsyon ağırlık paylaşımıyla bunu binlere indirir (CNN'in zaferi, Ders 32). Max pooling boyut azaltır, low-pass filtre gürültü giderir — ikisi de görüntü işlemenin standart adımları. ::: ## 3. Normal Matris: Ortogonal Özvektörlü Aile {#sec-normal-matris} Ortogonal özvektörlere sahip matrislerin tüm ailesinin adı: > *"...a matrix of that form is a normal matrix." — Strang, 32:20* **Normal matris:** $M = Q\Lambda Q^{*}$ (ortogonal/üniter özvektörler Q, herhangi karmaşık özdeğerler Λ). Test: M, eşlenik-transpozuyla değişmeli (commute): $$M^{*}M = MM^{*} \quad (\text{normal matris testi})$$ Bu aile simetrik ($A^{\top}=A$), diyagonal, ortogonal (real λ veya |λ|=1), antisimetrik (sanal λ) ve **sirkülant** matrisleri kapsar. Sirkülantlar neden normal? Çünkü **değişmelidirler**: > *"...circulant matrices commute. Any 2 circulant matrices commute." — Strang, 36:06* İki sirkülant $C_1 C_2 = C_2 C_1$ (ikisi de P'nin polinomu, polinomlar değişmeli). Dolayısıyla C ortogonal özvektörlere sahip — ayrıca hesaplamadan biliyoruz. ```{python} #| label: fig-normal-aile #| fig-cap: "Normal matris ailesi: M*M = MM* testi 5 üyede SIFIR (defect ≤ 4.44e-16), Jordan bloğunda 1.0 — sirkülantlar değişmeli olduğu için ailenin üyesidir (hesapsız kanıt)." #| fig-width: 10.5 #| fig-height: 4.2 #| code-fold: true fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(10.5, 4.2)) # Sol: 6 uye normality_defect bar (log olcek) fam = normal_family(seed=31) names = list(fam.keys()) defects = [max(normality_defect(M), 1e-17) for M in fam.values()] colors = [COL_PRIMARY] * len(names) # Jordan (degil) = turuncu for i, nm in enumerate(names): if "jordan" in nm.lower(): colors[i] = COL_VEC3 ax0.bar(range(len(names)), defects, color=colors) ax0.set_yscale("log") ax0.set_xticks(range(len(names))) ax0.set_xticklabels(names, rotation=20, ha="right") ax0.set_title("M*M = MM* testi: 5 uye SIFIR, Jordan = 1", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(ax0) # Sag: sirkulantlar degismeli heatmap |C1C2 - C2C1| = 0 rng = np.random.default_rng(7) C1 = circulant(rng.uniform(-2, 2, 4)) C2 = circulant(rng.uniform(-2, 2, 4)) comm = np.abs(C1 @ C2 - C2 @ C1) heatmap(ax1, comm, title="sirkulantlar degismeli: |C1C2 - C2C1| = 0", fmt="{:.0f}") fig.suptitle("Normal matris ailesi: ortogonal ozvektorun soyadi — sirkulantlar degismeli oldugu icin uyedir (hesapsiz kanit)", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` @fig-normal-aile aileyi ve değişmeliliği bir arada doğrular: solda altı üyenin $M^{*}M = MM^{*}$ defect'i — simetrik, diyagonal, ortogonal, antisimetrik ve sirkülant beşi sıfırda (defect ≤ **4.44e-16**, log-ölçek tabanında), Jordan bloğu [[1,1],[0,1]] ise **1.0** ile turuncu olarak ayrışır (normal **değil** — kontrast). Sağda iki rastgele sirkülantın değişmeliliği: $|C_1 C_2 - C_2 C_1|$ tam sıfır matristir (motorda $C_1 C_2 - C_2 C_1 < 1\text{e-}12$). İki sirkülant her zaman değişmeli olduğundan, sirkülantlar normaldir — ortogonal özvektörlere hesaplamadan sahip olduklarını biliriz. ::: {.callout-tip title="Builder Notu — Ortogonal Özvektörlülerin Soyadı"} "Normal matris = ortogonal özvektörlü aile, M*M=MM*" spektral teoremin (Ders 4) en geniş hâli: simetrik-ötesi, karmaşık özdeğerli ama hâlâ ortogonal özvektörlü. ML köprüsü: normal matrisler güvenli köşegenleştirme verir (kararlı, ortonormal taban); sirkülantların normal olması, Fourier tabanının (özvektörler) ortogonal olmasını garantiler — sinyal işlemenin sağlamlığı buradan. ::: ## 4. Özvektörler = w Kuvvetleri {#sec-w-kuvvetleri} C = P'nin polinomu olduğundan, C'nin özvektörleri = P'nin özvektörleri (Ders 30). P'nin özvektörleri çok özel — Fourier bağlantısı (çünkü periyodik): > *"...everything is going to be powers of w. e to the 2 pi i over N..." — Strang, 41:59* $$w = e^{2\pi i/n} \quad (\text{birim cemberin 1/n'i})$$ w, n'inci birim köküdür (karmaşık düzlemde dairenin 1/n'i kadar). λ=1 özvektörü (1,1,1,1); λ=−1 için (1,−1,1,−1); λ=i için (1, i, i², i³); λ=−i için (1, −i, (−i)², (−i)³). Her özvektörün bileşenleri w'nin kuvvetleri. P'yi (kaydırma) bir özvektörle çarpmak, onu w (veya bir kuvveti) ile ölçekler. ```{python} #| label: fig-w-kuvvetleri #| fig-cap: "Özvektörler w kuvvetleri: her kolon farklı frekansta kompleks üstel dalga — sinyali bunlara ayırmak = Fourier analizi. Solda n=8 birim çemberinde w = e^(2 pi i/8) kuvvetleri w^0..w^7; sağda F8 kolonlarının reel kısmı k=0..3 frekans dalgaları." #| fig-width: 10.5 #| fig-height: 4.4 #| code-fold: true fig, axes = plt.subplots(1, 2, figsize=(10.5, 4.4)) # --- Sol: n=8 birim çember + w kuvvetleri --- ax = axes[0] theta = np.linspace(0, 2*np.pi, 400) ax.plot(np.cos(theta), np.sin(theta), color=COL_STEEL_300, linewidth=1.0) n = 8 w = np.exp(2j * np.pi / 8) powers = w ** np.arange(n) ax.scatter(powers.real, powers.imag, s=100, color=COL_PRIMARY, zorder=5) for kk in range(n): p = powers[kk] ax.annotate(f"w^{kk}", (p.real, p.imag), textcoords="offset points", xytext=(8, 8), color=COL_TEXT, fontsize=10, fontweight="bold") ax.annotate("", xy=(powers[1].real, powers[1].imag), xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=COL_VEC3, linewidth=2.2)) ax.set_title("w = e^(2 pi i/8): 8 birim koku", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(ax) ax.set_aspect("equal") # --- Sağ: F8 kolonlarının reel kısmı = frekans dalgaları --- ax = axes[1] F8 = fourier_matrix(8) col_colors = [COL_ACCENT, COL_PRIMARY, COL_VEC3, COL_TEAL] for k in range(4): ax.plot(range(8), F8[:, k].real, marker="o", color=col_colors[k], label=f"k={k}") ax.legend() ax.set_title("F kolonlari = frekans dalgalari (Re kismi)", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(ax) fig.suptitle( "Ozvektorler w kuvvetleri: her kolon farkli frekansta kompleks ustel dalga — " "sinyali bunlara ayirmak = Fourier analizi", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.92]) plt.show() ``` @fig-w-kuvvetleri özvektörlerin geometrisini açar: solda $w = e^{2\pi i/8}$'in sekiz kuvveti $w^0, \dots, w^7$ birim çember üzerinde eşit aralıklı sekiz noktadır (her biri $|\cdot|=1$), $w^1$ turuncu okla vurgulanır — kaydırma P'nin özdeğer kümesi. Sağda F8 kolonlarının reel kısmı: k=0 sabit (DC bileşeni), k=1, 2, 3 giderek artan frekansta kosinüs dalgaları. Her kolon farklı frekansta bir kompleks üstel dalgadır; bir sinyali bu kolonlara ayırmak tam olarak Fourier analizidir. ::: {.callout-tip title="Builder Notu — Periyodiklik Fourier Doğurur"} "Özvektörler = w kuvvetleri, w = e^{2πi/n}" periyodikliğin Fourier'e dönüştüğü an. ML köprüsü: bu birim-kök özvektörleri sinüs/kosinüs dalgalarıdır (karmaşık üstel = frekans bileşenleri); bir sinyali bu özvektörlere ayırmak = Fourier analizi; CNN'lerin frekans-uzayı yorumu ve spektral filtreleme buradan. ::: ## 5. Fourier Matrisi F {#sec-fourier-matrisi} Tüm özvektörleri kolon kolon dizince **Fourier matrisi** F çıkar — ve bu, tüm sirkülantların özvektör matrisidir: > *"...Fourier matrix equals eigenvector matrix." — Strang, 43:39* $$F_{jk} = w^{jk}, \qquad w = e^{2\pi i/n}$$ (j, k = 0, 1, …, n−1; her girdi w'nin bir kuvveti, satır×sütun indisi.) İlk kolon hep 1; sonraki kolonlar w'nin artan kuvvetleri. > *"...the most important complex matrix in the world..." — Strang, 44:06* F'nin kolonları **ortogonaldir** (uzunluk $\sqrt{n}$); $F/\sqrt{n}$ ortonormaldir (normal matrisin ortogonal özvektörleri, §3). n=8 için son kolon $w^0, w^7, w^{14}, \dots, w^{49}$ ($w^{48}=1$ olduğundan $w^{49}=w$). ```{python} #| label: fig-fourier-f8 #| fig-cap: "Dünyanın en önemli kompleks matrisi F8: her girdi F_jk = w^jk bir faz çarkı (sol), kolonlar ortogonal — F^H F = 8I (sağ, defect 4.3e-14), uzunluk √8, F/√n üniter." #| fig-width: 11 #| fig-height: 4.6 #| code-fold: true fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(11, 4.6)) # Sol: F8 FAZ CARKI F8 = fourier_matrix(8) n = 8 # steel ince grid (hucre sinirlari) for x in range(n + 1): ax0.axvline(x - 0.5, color=COL_STEEL_300, linewidth=0.6, alpha=0.7) ax0.axhline(x - 0.5, color=COL_STEEL_300, linewidth=0.6, alpha=0.7) for j in range(n): for k in range(n): arg = np.angle(F8[j, k]) cx, cy = k, 7 - j # merkez (k, 7-j) dx = 0.35 * np.cos(arg); dy = 0.35 * np.sin(arg) ax0.annotate("", xy=(cx + dx, cy + dy), xytext=(cx - dx, cy - dy), arrowprops=dict(arrowstyle="->", color=COL_PRIMARY, lw=1.3)) ax0.set_xlim(-0.7, 7.7); ax0.set_ylim(-0.7, 7.7) ax0.set_aspect("equal") ax0.set_title("F8: her girdi w^(jk) — saat yonu faz carki", color=COL_TEXT, fontsize=12, fontweight="bold") ax0.axis("off") ax0.annotate("F[7,7] = w^49 = w", xy=(7, 0), xytext=(3.0, -0.5), color=COL_VEC3, fontsize=10, fontweight="bold", arrowprops=dict(arrowstyle="->", color=COL_VEC3, lw=1.2)) # Sag: |F^H F| heatmap FHF = np.abs(F8.conj().T @ F8) heatmap(ax1, FHF, title="F^H F = 8I: kolonlar ortogonal (defect 4.3e-14)", fmt="{:.0f}", fontsize=10) fig.suptitle("Dunyanin en onemli kompleks matrisi: F_jk = w^jk, kolonlar ortogonal uzunluk sqrt(8) — F/sqrt(n) uniter", color=COL_TEXT, fontsize=11, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.93]) plt.show() ``` @fig-fourier-f8 dersin amiral görselidir: solda F8'in her girdisi $F_{jk} = w^{jk}$ bir faz oku olarak çizilir — saat yönünde ilerleyen bir faz çarkı; köşe girdisi $F[7,7] = w^{49} = w$ ($w^{48}=1$ olduğundan, Notion örneğinin motor-teyitli sonucu) turuncu okla işaretlenir. Sağda $|F^{H}F|$ ısı haritası tam $8I$'dır: köşegende 8, köşegen-dışında 0 — kolonlar ortogonaldir, ortogonallik defect'i n=8 için yalnızca **4.3e-14** (n=2 için 1.2e-16, n=4 için 4.7e-16). Kolonların uzunluğu $\sqrt{8}$, dolayısıyla $F/\sqrt{n}$ üniterdir. ::: {.callout-tip title="Builder Notu — Bütün Frekanslar Tek Matriste"} "F = özvektör matrisi, $F_{jk}=w^{jk}$" sinyal işlemenin merkez nesnesi. ML köprüsü: F bir sinyali frekans bileşenlerine ayırır (DFT); kolonları farklı frekanslardaki karmaşık üstel dalgalar. Görüntü/ses sıkıştırma (JPEG/MP3), spektral filtreleme ve CNN'lerin Fourier-uzayı analizi hep F'ye dayanır. ::: ## 6. Köşegenleştirme ve FFT {#sec-kosegenlestirme-fft} Tüm sirkülantlar aynı F'de köşegenleşir: $$C = F\,\Lambda\,F^{-1}, \qquad \Lambda = \text{diag(c'nin Fourier donusumu)}$$ Özdeğerler Λ, ilk kolonun (c) **Fourier dönüşümü**dür (Fc). İşte konvolüsyon teoremi: C ile çarpmak (zaman uzayında evrişim) = F ile frekans uzayına git, Λ ile çarp (frekansta çarpma), F⁻¹ ile geri dön. Evrişim → çarpma. Ve **FFT** (hızlı Fourier dönüşümü), F·v çarpımını saf O(n²) yerine **O(n log n)**'de yapar — w kuvvetlerinin özyinelemeli yapısını kullanarak. ```{python} #| label: fig-konvolusyon-teoremi #| fig-cap: "Üç zafer tek satırda: $C = F\\Lambda F^{-1}$, evrişim çarpmaya döner (defect TAM 0.0), FFT $n\\log n$ — $n=1024$'te 102×. Sol C = F Lambda F^-1 rekonstrüksiyon defect'i 7.6e-16; orta FFT(c⊛d) ile FFT(c)·FFT(d) barları üst üste (defect 0.0); sağ FFT n log n vs DFT n² log-log, n=1024'te 102×, n=4096'da 341×." #| fig-width: 12 #| fig-height: 4 #| code-fold: true fig, axes = plt.subplots(1, 3, figsize=(12, 4)) c4 = np.random.default_rng(31).uniform(-2, 2, 4) d4 = np.array([4., 6, 1, 2]) # Sol: C = F Lambda F^-1 rekonstrüksiyon defect, lam = circulant_reconstruct_defect(c4) heatmap(axes[0], np.asarray(circulant(c4), float), title="C = F Lambda F^-1 (rekonstruksiyon 7.6e-16)", fmt="{:.2f}") # Orta: konvolüsyon teoremi — evrişim frekansta çarpmaya döner lhs = np.abs(np.fft.fft(cyclic_conv(c4, d4))) rhs = np.abs(np.fft.fft(c4) * np.fft.fft(d4)) x = np.arange(4) axes[1].bar(x - 0.18, lhs, width=0.36, color=COL_PRIMARY, label="FFT(c conv d)") axes[1].bar(x + 0.18, rhs, width=0.36, color=COL_VEC3, label="FFT(c) * FFT(d)") axes[1].set_title("evrisim = frekansta carpma (defect 0.0)", color=COL_TEXT, fontsize=12, fontweight="bold") axes[1].set_xticks(x); axes[1].set_xlabel("frekans indeksi k") axes[1].set_ylabel("genlik |.|"); axes[1].legend(fontsize=9) apply_style(axes[1]) # Sağ: FFT n log n vs DFT n² ölçek ns = 2**np.arange(4, 15) axes[2].loglog(ns, ns * np.log2(ns), color=COL_PRIMARY, marker="o", label="FFT n log n") axes[2].loglog(ns, ns**2.0, color=COL_VEC3, marker="s", label="DFT n^2") axes[2].axvline(1024, color=COL_STEEL_300, linestyle="--", linewidth=1.2) axes[2].annotate("n=1024: 102x", xy=(1024, 1024 * np.log2(1024)), xytext=(60, 4e6), fontsize=9, color=COL_TEXT) axes[2].annotate("n=4096: 341x", xy=(4096, 4096 * np.log2(4096)), xytext=(400, 6e7), fontsize=9, color=COL_TEXT) axes[2].set_title("FFT vs DFT olcek", color=COL_TEXT, fontsize=12, fontweight="bold") axes[2].set_xlabel("boyut n"); axes[2].set_ylabel("islem sayisi"); axes[2].legend(fontsize=9) apply_style(axes[2]) fig.suptitle("Uc zafer tek satirda: C = F Lambda F^-1, evrisim carpmaya doner (defect TAM 0.0), FFT n log n — n=1024 te 102x", color=COL_TEXT, fontsize=12, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.95]) plt.show() ``` @fig-konvolusyon-teoremi dersin üç zaferini tek figürde toplar: solda rastgele bir sirkülant C'nin $F\Lambda F^{-1}$ rekonstrüksiyonu — fark **7.6e-16** (köşegenleştirme kimliği tam), özdeğerler $\lambda = \text{np.fft.fft}(c)$ birebir (Ders 30'un köşegen=FFT(c) köprü-sayısının devamı). Ortada konvolüsyon teoremi: $|FFT(c \circledast d)|$ ile $|FFT(c) \cdot FFT(d)|$ barları üst üste oturur — evrişim frekansta çarpmaya döner, defect **tam 0.0** (n=4). Sağda FFT $n \log n$ ile DFT $n^2$ log-log eğrileri; n=1024'te oran **102×** (FFT 10.240 vs DFT 1.048.576), n=4096'da **341×** — n büyüdükçe açılan kazanç. ::: {.callout-note title="motor notu — w-yön konvansiyonu ve numpy DFT köprüsü"} Strang tahtada $\Lambda = Fc$ der; bizim motor kurulumumuzda (ilk-kolon c, aşağı-kaydırma P) özdeğerler $\lambda = \text{np.fft.fft}(c) = \sum_m c_m \, w^{-mk}$ olarak çıkar. Motor `circulant_reconstruct_defect` tam bunu döndürür: $\lambda = \text{np.fft.fft}(c)$. Gerçek c'de Strang'ın $Fc$'si ile numpy'ın `fft(c)`'si eşlenik kümedir (`Fc = conj(fft(c))`) — büyüklükler $|\lambda|$ aynı, yalnız w-yönü konvansiyonu (saat-yönü) farklı. İkinci tanık: numpy DFT köprüsü $\text{np.fft.fft}(v) = \text{conj}(F)\cdot v$ ($w^{-jk}$ konvansiyonu). Pedagojik öz değişmez — Notion'ın cümlesine sadık kalırız, [motor notu] yalnızca konvansiyon dalını kaydeder. ::: ::: {.callout-tip title="Builder Notu — Üç Zafer Tek Satırda"} "C = FΛF⁻¹, evrişim → çarpma, FFT O(n log n)" sinyal işlemenin üç zaferi tek satırda. ML köprüsü: büyük-çekirdek konvolüsyonlar FFT ile hızlandırılır (FFT-conv); ses modelleri (spektrogram), görüntü filtreleme ve bazı Transformer varyantları (FNet) Fourier dönüşümünü doğrudan kullanır. FFT, 20. yüzyılın en önemli algoritmalarından — sirkülant köşegenleştirmesinin meyvesi. ::: ## Bu Dersin Özeti {#sec-ozet-d31} - **Toeplitz vs sirkülant:** Toeplitz (sabit köşegen, döngüsüz) = evrişim; sirkülant = döngüsel evrişim. ML matrisleri böyle özel (ağırlık paylaşımı). - **ML görüntü:** milyon-piksel feature, 3M×3M tam matris imkansız → konvolüsyon + max pooling + low-pass filtre. - **Normal matris:** $M^{*}M = MM^{*}$; ortogonal özvektörlü aile (simetrik/diyagonal/ortogonal/antisimetrik/sirkülant). Sirkülantlar değişmeli → normal. - **Özvektörler:** $w = e^{2\pi i/n}$ kuvvetleri (birim kökleri); P'nin ve tüm sirkülantların özvektörleri. - **Fourier matrisi:** F = özvektör matrisi; $F_{jk} = w^{jk}$; kolonlar ortogonal (uzunluk $\sqrt{n}$), $F/\sqrt{n}$ ortonormal. - **Köşegenleştirme/FFT:** $C = F\Lambda F^{-1}$, $\Lambda = $ c'nin DFT'si; evrişim → çarpma (konvolüsyon teoremi); FFT $O(n \log n)$. ::: {.callout-important title="Tek Bir Cümle"} Tüm sirkülant matrisler aynı özvektör matrisini — Fourier matrisi F'yi ($F_{jk}=w^{jk}$, $w=e^{2\pi i/n}$) — paylaşır (çünkü normal ve değişmeli); bu matris her sirkülantı köşegenleştirir ($C=F\Lambda F^{-1}$), evrişimi çarpmaya çevirir (konvolüsyon teoremi) ve FFT'yi $O(n \log n)$ kılar. ::: ## Kontrol Soruları {#sec-sorular-d31} ::: {.callout-note collapse="true" title="Soru 1 — Toeplitz ve sirkülant farkı, ML'de hangisi çıkar"} İkisi de sabit-köşegenli (linear shift invariant). **Sirkülant** döngüseldir (köşeleri sarar) → döngüsel evrişim; **Toeplitz** döngüsüzdür → (sıradan) evrişim. ML'de genelde Toeplitz çıkar: CNN'in konvolüsyon katmanı aynı filtreyi tüm konumlara kaydırarak uygular (ağırlık paylaşımı), döngüsel değil. ::: ::: {.callout-note collapse="true" title="Soru 2 — Normal matris nedir, sirkülantlar neden normaldir"} Normal matris ortogonal/üniter özvektörlere sahiptir; test: $M^{*}M = MM^{*}$ (eşlenik-transpozuyla değişmeli). Simetrik, diyagonal, ortogonal, antisimetrik ve sirkülant matrisleri kapsar. Sirkülantlar normaldir çünkü **değişmelidirler** ($C_1 C_2=C_2 C_1$, ikisi de P'nin polinomu); dolayısıyla ortogonal özvektörlere sahip olduklarını hesaplamadan biliriz. ::: ::: {.callout-note collapse="true" title="Soru 3 — Fourier matrisi F'nin girdileri ve neden tüm sirkülantların özvektör matrisi"} $F_{jk} = w^{jk}$, $w = e^{2\pi i/n}$ (n'inci birim kökü); her girdi w'nin satır×sütun kuvveti. Tüm sirkülantlar P'nin polinomu olduğundan hepsi P'nin özvektörlerini paylaşır; bu özvektörler w'nin kuvvetlerinden kurulu = F'nin kolonları. Kolonlar ortogonal (uzunluk $\sqrt{n}$); $F/\sqrt{n}$ üniter (normal matrisin ortogonal özvektörleri). ::: ::: {.callout-note collapse="true" title="Soru 4 — C = FΛF⁻¹ neden evrişim = çarpma verir ve FFT'nin rolü"} C ile çarpmak (zaman uzayında evrişim) = F ile frekans uzayına git, Λ (diagonal, c'nin Fourier dönüşümü) ile çarp, F⁻¹ ile dön. Diagonal çarpma basittir → evrişim frekansta çarpmaya döner (konvolüsyon teoremi). FFT, F·v çarpımını O(n²) yerine $O(n \log n)$'de yapar (w kuvvetlerinin özyinelemeli yapısı); böylece evrişim/filtreleme çok hızlanır. ::: ## Egzersizler {#sec-egzersizler-d31} 1. **Birim kök.** n = 4 için $w = e^{2\pi i/4} = i$. $w^0, w^1, w^2, w^3$'ü hesapla (1, i, −1, −i). Bunların birim çember üzerinde 4 nokta olduğunu doğrula. (Motor tanığı: $w=i$ kuvvetleri $(1, i, -1, -i)$ — hepsi $|\cdot|=1$.) 2. **Fourier matrisi.** n = 2 için F (2×2) yaz: $w = e^{2\pi i/2} = -1$. $F_{jk} = w^{jk}$ ile $F = [[1,1],[1,-1]]$ olduğunu göster. Kolonlar ortogonal mi? Uzunlukları $\sqrt{2}$ mi? (Motor tanığı: $F(n{=}2) = [[1,1],[1,-1]]$; kolonlar ortogonal, uzunluklar $\sqrt{2}$ — birebir.) 3. **Normal test.** Sirkülant $C = [[2,1],[1,2]]$ (simetrik). $C^{*}C = CC^{*}$ mı? (Simetrik olduğundan normal mi?) Antisimetrik $[[0,1],[-1,0]]$ normal mi (eşlenik-transpozla değişmeli mi)? (Motor tanığı: $C=[[2,1],[1,2]]$ defect 0 → normal; antisimetrik $[[0,1],[-1,0]]$ defect 0 → normal.) 4. **Konvolüsyon teoremi.** İki sirkülantın çarpımı = döngüsel evrişim (Ders 30). Bu Fourier'de neye karşılık gelir? (İpucu: $C = F\Lambda F^{-1}$, çarpım → Λ'ların çarpımı → frekansta nokta-çarpım.) (Motor tanığı: $FFT(c \circledast d) = FFT(c)\cdot FFT(d)$, defect **tam 0.0** n=4'te ve <1e-10 n=3 Notion örneğinde.) 5. **(Ders 32 habercisi)** Fourier/sirkülant fikrini 2 boyuta (görüntü) taşı. Bir görüntüye uygulanan konvolüsyon nasıl çalışır? CNN'ler bunu nasıl katman katman kullanır? Bir tahmin yaz — Ders 32 "ImageNet bir CNN'dir, evrişim kuralı"nı işliyor. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d31} **Ders 32: ImageNet bir CNN'dir, Evrişim Kuralı.** Sirkülant/Fourier fikri 2B görüntüye genişler: konvolüsyonel sinir ağları (CNN). Evrişim kuralı (kaydır-çarp-topla), filtre/çekirdek, ağırlık paylaşımı; ImageNet'in CNN devrimini başlatması. fast.ai L15 (conv2d/im2col) ve NYU H6 (CNN) ile birebir köprü. ::: {.callout-warning title="Hazırlık"} Bu dersin Egzersiz 5'inin sorduğu soruyu zihninde tut: bu derste 1B sinyale uyguladığımız sirkülant/Fourier fikrini 2B görüntüye nasıl taşırsın? Ders 32, **konvolüsyonel sinir ağlarını** (CNN) işler — aynı filtre tüm görüntü konumlarına kaydırılarak uygulanır (Toeplitz ağırlık paylaşımı), max pooling boyutu düşürür, ve ImageNet'in CNN devrimi başlar. fast.ai L15 (conv2d/im2col) ve NYU H6 (CNN) bu dersle birebir köprü kurar. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d31} | Kavram | Formül / Fikir | Strang (dk) | |--------|----------------|-------------| | **DFT** | sirkülant ↔ ayrık Fourier dönüşümü | 2m49 | | Toeplitz | sabit köşegen, döngüsüz = konvolüsyon | 9m16 | | Normal matris | $M^{*}M = MM^{*}$; ortogonal özvektör | 32m20 | | Sirkülantlar değişmeli | $C_1 C_2 = C_2 C_1$ → normal | 36m06 | | Özvektörler = w kuvvetleri | $w = e^{2\pi i/n}$ (birim kökü) | 41m59 | | Fourier matrisi | F = özvektör matrisi; $F_{jk} = w^{jk}$ | 43m39 | | Köşegenleştirme/FFT | $C = F\Lambda F^{-1}$; evrişim → çarpma; $O(n \log n)$ | 44m06 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d31} - **Fourier matrisi = en önemli kompleks matris:** tüm sirkülantlar onda köşegenleşir → evrişim teoremi → FFT ($O(n \log n)$). - **CNN = Toeplitz konvolüsyon:** aynı filtre tüm konumlara (ağırlık paylaşımı); 3M×3M tam matris yerine küçük filtre; fast.ai L15 im2col/conv2d. - **Max pooling + low-pass:** boyut azaltma + gürültü giderme; görüntü işlemenin standart adımları. - **FFT-conv:** büyük-çekirdek konvolüsyon FFT ile hızlanır; ses (spektrogram), FNet (Fourier Transformer) doğrudan F kullanır. - **Normal matris/spektral:** ortogonal özvektörlü aile güvenli köşegenleştirme; graf sinyal işleme (spektral GCN, NYU paralel) Laplacian özvektörlerine genelleştirir. - **Geriye köprü:** Ders 30 (sirkülant/P/birim kökleri), Ders 3 (ortogonal Q), Ders 4 (özvektör matrisi/köşegenleştirme). Paralel: fast.ai L15 (convolution), NYU H6 (CNN). ::: {.callout-important title="Kapanış"} > *"...the most important complex matrix in the world..." — Strang, 44:06* Fourier matrisi tüm sirkülantların ortak özvektör tabanıdır; bu tek matris evrişimi çarpmaya çevirir, FFT'yi mümkün kılar ve sinyal işleme ile CNN'lerin köprüsüdür. :::