A matrix problem with line-sums

A matrix problem with line-sums

03:07:00  

Last week, one of my junior gave me a Linear Algebra / Matrix problem, which smell like a combinatorial problem (although until now, I haven't found a combinatorial proof of it).

Let $X$ and $Y$ be a $n \times n$  $(0,1)$-matrix , where the line-sums of $X$ (resp. $Y$) is equal to $k$ (resp. $k+1$). Suppose that  \begin{equation} XY=(k-\lambda)I_n + \lambda J\end{equation} where $J$ is the $n \times n$ matrix with all entries equal $1$, and $I_n$ is identity matrix. If $1+4(k-\lambda)$ is not a perfect square prove that $n=4\lambda +1$ and $k=2 \lambda$.  

Here is a combinatorial version of the above

Let $A=\{1,2,..,n\}$ and suppose that we have $2n$ subsets of $A$, say $X_1, X_2, ..., X_n$ and $Y_1, Y_2, ..., Y_n$, where each subsets satisfy:

• $|Y_i| = |X_i|+1 = k+1$ for all $i=1,2,...,n$.

• For each $x \in A$, there are exactly $k$ subsets $X_{i_1}, X_{i_2}, ..., X_{i_k}$ and exactly $k+1$ subsets $Y_{i_1}, Y_{i_2}, ..., Y_{i_{k+1}}$ which contain $x$.

•  For any $i=1,2,..,n$ we have $|X_i \cap Y_i| = k$ and while for any $1 \leq i < j \leq n$ we have $|X_i \cap Y_j| = \lambda$.

If $1+4(k-\lambda)$ is not a perfect square prove that $n=4\lambda +1$ and $k=2 \lambda$.

After awhile I found a proof using eigenvalues. But now,  I'm actually interested on a combinatorial proof of this one,  the condition $1+4(k-\lambda)$ condition seems to be does not have any trivial combinatorial interpretation.

But I will give a sketch of Linear-Algebra proof on this post.
Notice that the Right-Hand-Side is just the matrix
\[H(k,\lambda)=\begin{pmatrix} k & \lambda & \cdots & \cdots & \lambda \\ \lambda & k &\cdots & \cdots & \lambda \\ \lambda & \lambda & \ddots & \cdots & \lambda \\ \vdots & \vdots & \ddots &\ddots & \vdots \\ \lambda & \lambda &\cdots & \cdots & k\end{pmatrix}\]

The $i$-th diagonal entry of this matrix which is equal to $k$, is just the dot product between the $i$-th row of $X$ and $i$-th column of $Y$,  both according to the problem with total sum $k$ and $k+1$. 

From this we can deduce that the $i$ -th column of $Y$ is just a nearly exact copy of $i$-th row of $X$, they only differ in one non-zero entry, let's call these entries speciality .  

If we separate these so called specialities into a separated matrix $P$, we will get

\[Y = X^T + P\]

where $P$ contains the separated specialities.  Furthermore, $P$ is a permutation matrix, namely there is exactly single $1$ on each column  and exactly single $1$ on each row  (since otherwise $Y$ would have a row/column with total sum greater than $k+1$)

Now,  we can make $P$ into an identity matrix by right-multiplying $Y$ with some permutation matrices, recall that the right-multiplication of a matrix with permutation matrix will permute the column of the given matrix, while the left multiplication will permute the row.  

So choosing permutation matrices $\mathcal{P} = P_1 P_2  \cdots P_m$ where each $P_i$ is a transposition (i.e obtained by interchanging two columns of identity matrix) we make $P \mathcal{P} = I$.  

This make $Y$ into $B = X^T  \mathcal{P} + I = (\mathcal{P}^T X)^T + I$ 

Observe that $\mathcal{P}^T = P_m^T P_{m-1}^T \cdots P_1^T = P_m P_{m-1} \cdots P_1$ , since each transposition is symmetric.  

Putting $A=(P_m P_{m-1} \cdots P_1 X)$, we see that $A$ is just a row permuted from $X$, and so the condition of  line-sum equals $k$ is still intact. Furthermore, we also make all diagonal entries of $A$ become zero, since by moving those specialities on $Y$ into diagonal, we also moving the respective zeros related to the speciality into the diagonal of $X$. 

\[ A (A^T + I) = P_m P_{m-1} \cdots P_1 (H(k,\lambda)) P_1 P_2 \cdots P_m\]

but $P_m P_{m-1} \cdots P_1(H(k,\lambda)) P_1 P_2 \cdots P_m = H(k, \lambda)$, this because if we interchange the $i$-th column  and  the $j$-th column of $H(k,\lambda)$  and then interchange $i$-th row and $j$-th row, we will back again to $H(k, \lambda)$.  

So we have equation

\[AA^T+A = H(k,\lambda)\]

Taking the transpose of both sides we have $A^T = A$, and so the equation becomes $A^2+A = H(k, \lambda)$, with $trace(A)=0$ and line-sums of $A$ is all $k$. 

Now being a symmetric matrix, $A$ is (orthogonally) diagonalizable, and we can transform the above equation into

\[D^2 + D = W\]

where $D$ is diagonal matrix which consists eigenvalues of $A$, and diagonal matrix $W$ which consists the eigenvalues of  $H(k, \lambda)$.

The eigenvalues of $H(k,\lambda)$ are easy too obtain, indeed, by simple calculation we may check that $(1,-1, 0, 0, ... , 0)^T$, $(0,1,-1, 0, ..., 0)^T$, ..., $(0,0,0,0..., 1, -1)^T$, and $(1,1,1,...,1)^T$ are linearly independent eigenvectors of  $H(k, \lambda)$ with eigenvalues $\underbrace{k-\lambda, k-\lambda, ..., k-\lambda}_{k \, many}$ and $k+\lambda(n-1)$, respectively.

The eigenvalues of $A$, is less trivial, observe that since row sum of $A$ is $k$, we know that $k$ is an eigenvalue of $A$ with eigenvector $(1,1,1,1,...,1)^T$. 

Let say the (multi)-set of eigenvalue of $A$ is $\sigma(A)= \{k, l_1, l_2, ... , l_{n-1}\}$ (sometime called spectrum of $A$), so $\sigma(D^2+D) = \{k^2+k , l_1^2+l_1, ... , l_{n-1}^2+l_{n-1}\} $ we must have

\[\{k^2+k , l_1^2+l_1, ... , l_{n-1}^2+l_{n-1}\} = \{k-\lambda, k-\lambda, ..., k-\lambda , k+(n-1)\lambda\}\]

Let start with $k^2+k$, if $k^2+k=k-\lambda$, we will have $k^2=-\lambda$, this can't be right since $\lambda$ is non-negative and $k$ is non-zero.  So we must have $k^2+k = k+(n-1)\lambda$, and we have

\[k^2= (n-1) \lambda\]

Now then we also have $l_i^2+l_i = k-\lambda$, thus we get

\[l_i = \frac{-1+\sqrt{1+4(k-\lambda) }}{2} \qquad \text{or} \qquad l_i= \frac{-1-\sqrt{1+4(k-\lambda) }}{2}\]

But since  $1+4(k-\lambda)$ is not a square $l_i$ is irrational number. But from $trace(A)=0$ we also have 

\[k+l_1 + l_2 + ...  + l_n = 0\]

so the sum of these irrational numbers is an integer, thus they must occurs in conjugate pairs. It means that exactly $\frac{n-1}{2}$ of $l_i$ is $\frac{-1+\sqrt{1+4(k-\lambda) }}{2}$ while the other $\frac{n-1}{2}$ is $\frac{-1-\sqrt{1+4(k-\lambda) }}{2}$. 

Now each conjugate pairs summed to $-1$, so we must have $l_1 + l_2 + ... + l_{n-1} = -\frac{(n-1)}{2}$.  Therefore

\[k-\frac{n-1}{2}=0 \Rightarrow n=2k+1\]

Substituting this into $k^2=(n-1)\lambda$ we will get $k=2\lambda$, furthermore back substitution will yield $n=4\lambda +1$, and we are done. 

Update: I typed a quite-long formally written proof in this pdf file.

Continue Reading

Lanjutan Exact Kanan dari Tensor Product.

Lanjutan Exact Kanan dari Tensor Product.

21:00:00  

Akhirnya saya sudah bisa menggambar commutative diagram, mari kita lanjutkan bukti bahwa fungtor $(\cdot) \otimes N$ adalah exact kanan.

Untuk kemudahan penulisan, karena $Hom(N,P)$ juga merupakan $R$-Module, kita definisikan $\mathfrak{F}_X(M) = Hom(M,Hom(N,P))$, dimana $\mathfrak{F}_X(M')$ dan $\mathfrak{F}_X(M'')$ didefinisikan secara similar. 

Perhatikan diagram
\[\xymatrix{ M \ar[d] \ar[r]^f & M^{\prime} \ar[d] \ar[r]^g & M^{\prime \prime} \ar[d] \ar[r] & 0 \ar[d] \\ \mathfrak{F}_X(M) \ar[d]^{\psi} & \mathfrak{F}_X(M') \ar[l]_{\varphi_f(\lambda) = \lambda \circ f} \ar[d]^{\psi'} & \mathfrak{F}_X(M'') \ar[l]_{\varphi_g(\mu) = \mu \circ g} \ar[d]^{\psi''} &0 \ar[d]\ar[l] \\ Hom(M \otimes N, P)\ar[d] &Hom(M^{\prime} \otimes N, P)\ar[d] \ar[l]_{v} & Hom(M^{\prime \prime} \otimes N, P) \ar[l]_{w} \ar[d] &0 \ar[l] \ar[d] \\ M \otimes N \ar[r] & M^{\prime} \otimes N \ar[r] & M^{\prime \prime} \otimes N \ar[r] &0} \]

Kita akan "menginduksi" ke-exact-an dari baris pertama pada diagram diatas, ke baris kedua, ketiga dan keempat.

Catatan bahwa module $P$ pada diagram diatas adalah "sebarang module",  ini berarti baris ketiga/kedua dibaca  "exact untuk sebarang module $P$".

Perhatikan bahwa pemetaan $\psi, \psi^{\prime}$ dan $\psi^{\prime \prime}$ diperoleh dari fungtoriality di post sebelumnya, dan seperti yang telah dibuktikan semuanya merupakan isomorphism, kita definisikan pemetaan $w$ dan $v$ sebagai: 

\[w = \psi^{\prime} \circ \varphi_g \circ (\psi^{\prime \prime} )^{-1} \qquad v = \psi \circ \varphi_f \circ (\psi^{\prime})^{-1}\]

yakni kita membuat ketiga kotak ditengah membentuk diagram komutatif, atau dengan kata lain disini $\psi, \psi^{\prime}$ dan $\psi^{\prime \prime}$ adalah komponen Natural Transformation dari fungtor $\mathfrak{F}$ ke fungtor $((\cdot) \otimes N, P)$.

Hal ini dapat digunakan untuk membuktikan bahwa baris ketiga dari diagram diatas membentuk barisan exact. 

Baris 1 exact $\Longrightarrow$ Baris 2 exact

Kita pakai hasil  berikut :

Untuk sebarang $X \in Mod_R$, contravariant functor $\mathfrak{F}_X : Mod_R \rightarrow Mod_R$ yang diberikan $M \rightarrow Hom(M, X)$, adalah exact kanan, yakni
\[\xymatrix{ M \ar[r]^f & M^{\prime} \ar[r]^g & M^{\prime \prime} \ar[r] & 0 }\]
adalah barisan exact maka barisan \[\xymatrix{0 \ar[r] & Hom(M'',X) \ar[r]^{\varphi_g(\mu)=\mu \circ g} & Hom(M',X) \ar[r]^{\varphi_f(\lambda)=\lambda \circ f} & Hom(M,X)} \]
juga exact. 

Bukti: 

Pertama-tama kita buktikan $ker(\varphi_g) = \{0\}$, ini mudah karena jika $\varphi_g(\mu)=0$ maka diperoleh $(\mu \circ g)(m) = 0$ untuk setiap $m \in M'$, tapi karena $g$ surjective maka ini berarti untuk setiap $m_2 \in M^{\prime \prime}$ berlaku $\mu(m_2) = 0$, sehingga $\mu=0$, terbukti  $ker(\varphi_g) = \{0\}$. 

Selanjutnya akan dibuktikan $ker(\varphi_f) = img(\varphi_g)$. Untuk $\varphi_g(\lambda) \in img(\varphi_g)$ dimana $\lambda \in Hom(M'', X)$, diperoleh \[\varphi_f(\varphi_g(\lambda)) = (\varphi_g(\lambda)) \circ f = \lambda \circ  g \circ f\]

tapi karena $img(f) = ker(g)$, maka $\lambda \circ g \circ f = 0$, sehingga diperoleh $\varphi_g(\lambda) \in ker(\varphi_f)$, jadi $img(\varphi_g) \subseteq ker(\varphi_f)$. 

Misalkan $\lambda \in Hom(M',X)$ sedemikian sehingga $\varphi_f(\lambda)=0$,  diperoleh $(\lambda \circ f)(m) = 0$ untuk setiap $m \in M$.  Kita harus membuktikan $\lambda \in img(\varphi_g)$, yakni terdapat $\mu \in Hom(M^{\prime \prime}, X)$ sedemikian sehingga $\mu \circ g = \lambda$.  Kita definisikan saja $\mu$ sebagai:

\[\mu(x) = \lambda(y) \qquad \text{Jika $x=g(y)$ }\]

perhatikan bahwa eksistensi dari $y$ diberikan oleh sifat surjective dari $g$, agar $\mu$ well-defined misalkan $g(y_1)=x_1$ dan  $g(y_2)=x_2$ dimana $x_1=x_2$ maka 

\[0=x_1-x_2 = g(y_1) - g(y_2) = g(y_1-y_2)\]

jadi $y_1-y_2 \in ker(g) = img(f)$, sehingga diperoleh $y_1-y_2 = f(m)$ untuk suatu $m \in M$, ini berarti \[\lambda(y_1-y_2) = \lambda (f(m)) = (\lambda\circ f)(m) = 0 \Longrightarrow \lambda(y_1) = \lambda(y_2) \Longrightarrow \mu(x_1)=\mu(x_2)\]

Jadi $\mu$ well-defined dan merupakan linear map karena komposisi dari dua linear map, terlebih lagi untuk setiap $y \in M^{\prime}$ diperoleh  $(\mu \circ g)(y) = \mu(g(y)) = \lambda(y)$.  $\blacksquare$.

Dengan menggunakan $X=Hom(N,P)$ pada teorema diatas, maka kita peroleh baris 2 diagram diatas exact apapun $R$-module $P$ nya.

Baris 2 exact  $\Longrightarrow$ Baris 3 exact untuk setiap $P$

Perhatikan bahwa $w = \psi^{\prime} \circ \varphi_g \circ (\psi^{\prime \prime} )^{-1}$, yakni komposisi dari pemetaan injective, maka $w$ juga injective.  Lalu karena $v \circ w = \psi \circ \varphi_f \circ \varphi_g \circ (\psi^{\prime \prime} )^{-1}$ dan $img(\varphi_g) = ker(\varphi_f)$ maka untuk setiap $x \in Hom(M^{\prime \prime} \otimes N,P)$ berlaku \[(v \circ w)(x) = \psi \circ \varphi_f \circ (\varphi_g ( (\psi^{\prime \prime} )^{-1} (x)) ) = \psi(0) = 0 , \]
jadi $img(w) \subseteq ker(v)$.

Sebaliknya untuk setiap $x \in Hom(M^{\prime} \otimes N,P)$ dengan $v(x)=0$ , maka
\[(\varphi_f \circ (\psi^{\prime})^{-1} ) (x) = (\psi^{-1} \circ v )(x) = \psi^{-1}(0) = 0\]

sehingga diperoleh $(\psi^{\prime})^{-1} (x) \in ker (\varphi_f) = img(\varphi_g)$.

Ini berarti
\[(\psi^{\prime})^{-1} (x) = \varphi_g (\mu) \text{ untuk suatu } \mu \in \mathfrak{F}_X(M'') \Longrightarrow x = \psi^{\prime} \circ \varphi_g (\mu) \] Misalkan $ y = \psi^{\prime \prime}(\mu)$, dengan sifat isomorphism diperoleh $\mu =( \psi^{\prime \prime})^{-1}(y)$, sehingga \[x= \psi^{\prime} \circ \varphi_g \circ( \psi^{\prime \prime})^{-1}(y) = w(y) \] sehingga $x \in img(w)$.

Baris 3 exact untuk setiap $P$ $\Longrightarrow$ Baris 4 exact

Kita akan buktikan

Misalkan $A$, $B$, dan $C$ adalah $R$-module maka jika untuk setiap $X$ barisan
 \[\xymatrix{& Hom(C',X) \ar[r]^{\varphi_g(\mu)=\mu \circ g} & Hom(B,X) \ar[r]^{\varphi_f(\lambda)=\lambda \circ f} & Hom(A,X)} \]
 exact maka diperoleh
\[\xymatrix{ A \ar[r]^f & B \ar[r]^g & C}\]
juga exact

Bukti:

Kita gunakan cara yang sama ketika membuktikan Lemma Yoneda. Karena hipotesa menyatakan berlaku untuk semua $X$, maka kita boleh melihat ketika $X=C$. Ini berarti 

\[g= id_{C} \circ g = \varphi_g( id_{C} ) \in img(\varphi_g) = ker(\varphi_f)\]

Sehingga $\varphi_f(g)=0$, jadi $g \circ f = 0 $, diperoleh $img(f) \subseteq ker(g)$. 

Kita kemudian pilih $X$ sedemikian sehingga terdapat linear map $\lambda : B \rightarrow X$ mempunyai kernel tepat sama dengan $img(f)$. Hal ini diberikan oleh pemetaan canonical $\lambda: B \rightarrow B/ img(f)$,  $b \rightarrow img(f)+b$.   

Dengan pemetaan canonic diatas $(\lambda \circ f)(a) = img(f)+f(a) = img(f)=0$, jadi pemetaan canonic merupakan anggota $ker(\varphi_f)=img(\varphi_g)$, sehingga diperoleh $\lambda = \mu \circ g$ untuk suatu $\mu \in Hom(C, B/img(f))$. Sedangkan untuk setiap $m_1 \in ker(g)$, kita peroleh $0=(\mu \circ g)(m_1) = \lambda(m_1)$, jadi $m_1 \in ker(\lambda)=img(f)$, sehingga terbukti $ker(g) \subseteq img(f)$. $\blacksquare$

q.e.d

Apabila kita gunakan teorema diatas dengan $(A,B,C)=(M\otimes N, M^{\prime} \otimes N, M^{\prime \prime} {\otimes} N)$ dan ketika $(A,B,C) = ( M^{\prime} \otimes N, M^{\prime \prime} \otimes N , 0)$ maka diperoleh

\[\xymatrix{M \otimes N \ar[r] & M^{\prime} \otimes N \ar[r] & M^{\prime \prime} \otimes N \ar[r] &0}\]

barisan  exact.

Continue Reading

Tensor Product sebagai Fungtoriality

Tensor Product sebagai Fungtoriality

19:53:00  

Semalam, ketika mendiskusikan tentang contoh Sheafification. Pak Fajar bilang bahwa itu diberikan dari left-adjoint functor $L: PSh(\mathcal{C}) \rightarrow Sh(\mathcal{C})$ dari inklusi $Sh(\mathcal{C}) \hookrightarrow Psh(\mathcal{C})$.

Karena bahasa Category saya belum lancar, saya mencoba mencari kasus-kasus less abstract yang saya kenal dari -so called- adjoint functor. Anyway pada definisi yang diberikan  (bukan full definition) terdapat isomorphism

\[ Hom_\mathcal{D} (L(C),D) \simeq Hom_\mathcal{D} (C,R(D)) \]

untuk $C \in \mathcal{C}$ dan $D \in \mathcal{D}$.

Dulu sekali, saya pernah mengerjakan sebuah latihan tentang right exactness dari Tensor Product terhadap suatu $R$-module $N$. (Sepertinya ada di Attiyah), yaitu

Untuk $R$-module $A$, $B$, dan $C$, jika
\[A \rightarrow B \rightarrow C \rightarrow 0 \]
adalah barisan exact maka
\[A \otimes N \rightarrow B \otimes N \rightarrow C \otimes N \rightarrow 0\]
juga barisan exact. 

Pada buktinya, terdapat (hint?) untuk membuktikan hal ini terlebih dahulu:

Untuk $R$-module $M$, $N$, dan $P$ maka berlaku
\[Hom_R(M \otimes N, P) \simeq Hom_R(M , Hom_R(N, P)) \]

In other words, dalam bahasa Category,  kita punya functor $\mathcal{F} : Mod_R \rightarrow Mod_R$ diberikan dengan $(\cdot) \otimes N$ dan functor $\mathcal{G} : Mod_R \rightarrow Mod_R$ diberikan dengan $Hom(N, \cdot)$ dan mereka memenuhi bentuk yang saya berikan diatas.

Bukti:

Definisikan $\Psi : Hom_R (M \otimes N, P) \rightarrow Hom_R (M , Hom(N, P)) $
dengan aturan:

Untuk $f: M \otimes N  \rightarrow P$, hasil pemetaan dari $\Psi(f)$ adalah fungsi $g$  yang memetakan $x \in M$ ke fungsi $g(x) : N \rightarrow P$, dimana $g(x)$ memetakan $y \in N$ ke $[g(x)](y)=f(x \otimes y)$.

Singkatnya kita tulis

\[\Psi(f)(x)(y) = f(x \otimes y) \qquad x\in M \, , \, y\in N\]

   Pembuktian bahwa $[g(x)](y) = f(x \otimes y)$ adalah benar anggota $Hom_R(N, P)$ , cukup rutin dengan menggunakan sifat billinear dari tensor product.   Pembuktian bahwa $g(x)$ adalah benar anggota $Hom_R (M , Hom(N, P))$ juga cukup jelas dengan sifat billinear dan sifat linear dari $f$.
Pembuktian bahwa $\Psi$ injective (monomorphism) juga tidak begitu sulit.

Yang menarik adalah pembuktian bahwa $\Psi$ surjective, saya akan coba jabarkan.

Ambil sebarang $g \in Hom_R(M, Hom_R(N,P))$, kita akan membuktikan terdapat $f \in Hom_R(M \otimes N, P)$ sedemikian sehingga $\Psi(f) = g$. Perhatikan bahwa $g$ memetakan anggota $x\in M$ ke anggota $Hom_R(N, P)$.

Kita akan menggunakan Universal Property dari Tensor Product, yaitu dimulai dari mendefinisikan billinear map $f^{\prime} : M \times N \rightarrow P$ sebagai berikut:
\[f^{\prime}(x,y) = g(x)(y)\]

Karena $g$ linear maps maka $f^{\prime}(ax_1+bx_2 ,y ) = g(ax_1 +bx_2))(y) = g(ax_1)(y)+g(bx_2)(y) = [ag(x_1)](y)+[bg(x_2)](y)$, secara similar ini juga berlaku untuk variabel $y$. Sehingga diperoleh $f^{\prime}$ adalah fungsi billinear.

Jadi dengan Universal Property dari Tensor Product (maaf saya belum bisa gambar commutative diagram di blogger)  terdapat unique $f \in Hom_R(M \otimes N, P)$ sedemikian sehingga

\[\Psi(f)(x)(y) = f(x \otimes y) = f^{\prime}(x,y) = g(x)(y)\]

terbukti.

Saya ingin lanjut ke right-exactness agar relevant ke adjoint functor, dan saya bisa lebih mengerti secara lebih natural tentang adjoint functor,  tapi saat ini belum tahu cara mengetik commutative diagram dengan nyaman di Mathjax :[

Continue Reading

Soal Batu

Soal Batu

03:47:00  

Beberapa bulan yang lalu, di olimpiade.org, sayakalah (Erlang) mem-posting soal berikut:

Diberikan $2n+1$ buah batu dengan berat bilangan real positif. Untuk setiap $1 \leq i \leq 2n+1$, apabila batu dengan berat $a_i$ kita pisahkan, maka $2n$ buah batu sisanya dapat dikelompokan menjadi dua grup dengan $n$ anggota, dimana berat total kedua grup batu tersebut sama. Buktikan bahwa berat batu sama semua. 

Bagi saya soal ini sangat susah, karena beratnya yang harus bilangan real positif.  Saya menyelesaikan soal ini dengan menggunakan Hamel Basis, dan argumen yang similar juga berlaku ketika "berat" batu boleh bilangan  negatif. (solusi saya di olimpiade.org dapat dilihat dengan mengklik soal diatas, saya=Adri :p )

Beberapa hari yang lalu, saya melihat soal serupa yang relatif lebih mudah dimana berat batu adalah bilangan bulat positif, yang merupakan soal Kompetisi Putnam ke-34 (saya kurang tahu Putnam tahun berapa itu, google saja).  (Update: Soal yang sama ternyata juga ada di buku The USSR OLYMPIAD PROBLEM BOOK oleh Shklarsjy, Chentzov, Yaglom). Soal versi bilangan real ini muncul (tanpa solusi) di buku Problems From The Book, dan ada di bab yang membahas tentang Dirichlet Approximation (Kronecker's Theorem  dan kawan2). Mungkin perlu dicoba mencari solusi yang menggunakan Dirichlet Approximation.

Argumen yang saya pakai di olimpiade.org ternyata bisa  mengeneralisasi soal ini dimana "berat" batu  merupakan Matriks berukuran $n \times n$ dengan komponen matriks berupa bilangan-bilangan kompleks, sebenarnya argumen saya juga berlaku untuk sebarang ruang vektor atas lapangan kompleks.

Untuk kemudahan, seperti pada post di olimpiade.org, kita sebut syarat :

"Jika diambil sebarang satu anggota, sisanya dapat dipartisi menjadi dua grup sama banyak dengan total kuantitas sama besar"

sebagai syarat bagus.

Kita telah membuktikan bahwa jika $2n+1$ buah bilangan real memenuhi syarat bagus maka $2n+1$ buah bilangan tersebut akan sama.

Dengan argument yang sama, kita akan buktikan untuk kasus bilangan kompleks.

Misalkan $z_j=x_j + i y_j$ untuk $j=1,2, \cdots, 2n+1$ adalah bilangan kompleks yang memenuhi syarat bagus. Maka berlaku $z_1=z_2= \cdots = z_{2n+1}$.

Solusi: Perhatikan bahwa apabila $z_k$ diambil, maka dengan syarat bagus kita peroleh terdapat dua himpunan disjoint $A_k, B_k \subseteq \{z_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ dan memenuhi

\[\sum_{j \in A_k} x_j + i \left( \sum_{j \in A_k} y_j \right) = \sum_{j \in B_k} x_j + i \left( \sum_{j \in B_k} y_j \right) \]

Ini berarti $\sum_{j \in A_k} x_j = \sum_{j \in B_k} x_j$ dan $\sum_{j \in A_k} y_j = \sum_{j \in B_k} y_j$, dengan kata lain bilangan real $x_1, x_2, \cdots, x_{2n+1}$ dan $y_1, y_2, \cdots, y_{2n+1}$ memenuhi syarat bagus, dan karena kita sudah membuktikan soal untuk bilangan real, maka diperoleh $x_1 = x_2 = \cdots = x_{2n+1}$ dan $y_1 = y_2 = \cdots =y_{2n+1}$. Dari sini kita peroleh $z_1 = z_2= \cdots = z_{2n+1}$ dan kita selesai. $\blacksquare$

Sekarang jelas bahwa argumen yang similar dapat digunakan apabila berat batu adalah anggota dari ruang vektor berdimensi hingga  $V$ atas lapangan $\mathbb{C}$.

Diberikan $\mathbf{w}_1 , \mathbf{w}_2, \cdots, \mathbf{w}_{2n+1}$ adalah vektor-vektor di $V$ yang memenuhi syarat bagus.  Misalkan $\mathbf{b}_1, \mathbf{b}_2, \cdots, \mathbf{b}_{m}$ adalah basis dari $V$.  Kita tulis

\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i\]

dimana $\alpha_{si} \in \mathbb{C}$ untuk $1 \leq s \leq 2n+1$ dan $1 \leq i \leq m$.


Maka jika $\mathbf{w}_k$ dibuang,  dari syarat bagus  sisanya dapat dipartisi menjadi dua himpunan disjoint $A_k, B_k \subseteq \{\mathbf{w}_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ yang memenuhi

\[\left( \sum_{j \in A_k} \alpha_{j1} \right) b_1 +  \cdots + \left( \sum_{j \in A_k} \alpha_{jm} \right) b_m = \left( \sum_{j \in B_k} \alpha_{j1} \right) b_1 + \cdots + \left( \sum_{j \in B_k} \alpha_{jm} \right) b_m \]

Ini berarti untuk setiap $i \in \{1, 2, \cdots, m\}$ bilangan kompleks $\alpha_{1i}, \alpha_{2i}, \cdots, \alpha_{2n+1 i}$ memenuhi syarat bagus, sehingga $\alpha_{1i}=\alpha_{2i}= \cdots=\alpha_{2n+1 i}$. Jadi diperoleh untuk sebarang $s, t \in {1, 2, \cdots, 2n+1}$ berlaku

\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i = \sum_{i=1}^m \alpha_{ti} \mathbf{b}_i = \mathbf{w}_{t}\]

dan kita selesai.

Dari sini kita bisa melihat bahwa jika "berat" batu merupakan vektor, matriks, atau bahkan ketika batu tersebut mempunyai "berat"  polynomial, jika syarat bagus terpenuhi maka berat mereka sama.


Sebenarnya (mungkin )kita bisa mengeneralisasi lebih jauh, pada artikel "A Combinatorial Generalization of a Putnam Problem" oleh Ömer Egecioglu, di American Mathematical Monthly, dia membuktikan (dengan menggunakan Cyclotomic Polynomial ) pernyataan berikut:

Misalkan $\xi$ sebuah akar primitif dari $x^q-1$ dimana $q=p^r$, dan $p$ adalah bilangan prima. Diberikan barisan $S$ yang terdiri dari $qn+1$ buah bilangan komplex $z_1, z_2, \cdots, z_{qn+1}$ dengan sifat :  Untuk setiap $i \in \{1, 2, \cdots qn+1\}$. $S \backslash \{z_i\}$ dapat di partisi menjadi $q$ buah himpunan sama besar $S_{i0}, S_{i1}, \cdots, S_{i, q-1}$ dengan
\[\sum_{k=0}^{q-1} \xi^k \sum_{z_j \in S_{t,k}} z_j=0\]
maka $z_1 = z_2 = \cdots = z_{qn+1}=0$

Ketika $k=1$ dan $p=2$, kita peroleh versi bilangan kompleks yang telah kita buktikan diatas.

Jika digabung dengan argumen saya yang sebelumnya, teorema diatas harusnya juga berkerja untuk sebarang ruangan vektor atas bilangan kompleks. [ya kan? :p ]

Continue Reading

Aftermath dan Beforemath Mario di ISMOC.

Aftermath dan Beforemath Mario di ISMOC.

00:04:00  

Beberapa hari yang lalu, saya mengajukan sebuah soal di lomba ISMOC, yang ternyata semalam sebelum lomba, diberi counter-example oleh Erlang Wiratama Surya T_T.  Tapi untungnya kita beri sebuah phrase sehingga bisa dikerjakan.


Karena soalnya berasal dari sebuah argument extermal (karena saya bikin soalnya pakai argument dulu, trus ditambah macam-macam baru jadi soal), akhirnya kita memberikan tambahan kata-kata pada soalnya agar argument extermal saya tetap jalan. Tambahannya cukup minim yaitu ""beserta sebuah kanal dari $G$ ke $X$"" seperti pada soal dibawah (huruf tebal menyatakan ralat yang ditambahkan).

Walaupun sebenarnya, karena sudah mengantuk, kita melakukan argument ekstermal pada directed graph menggunakan arah yang berbeda dengan yang diberikan soal, dan untungnya suatu struktur pada soal merupakan sebuah cycle, jadi pada akhirnya arahnya tidak begitu ngaruh, dan soal masih benar, ini hoki maksimal sih :p.

Saya minta maaf atas kesalahan ini, dan berterima kasih kepada Erlang yang sudah mau berdiskusi sampai jam 2 subuh pada malam sebelum lomba.
Pada saat lomba, terdapat dua orang yang berhasil menyelesaikan soal ini dengan sempurna.

Mario sedang berada  pada Negeri Jamur yang mempunyai $n$ buah kota. Beberapa dari kota tersebut terhubung oleh saluran pipa yang mempunyai arus satu arah, pipa-pipa ini dapat digunakan sebagai sarana transportasi antar kota, namun Mario tidak bisa berpindah melawan arus pada pipa-pipa tersebut, sehingga setiap pipa hanya berlaku sebagai jalan satu arah.  Diketahui bahwa untuk setiap kota, banyak pipa dengan arus menuju keluar kota sama banyak dengan banyak pipa dengan arus menuju masuk ke kota tersebut.  

Suatu hari pada kota $P$, Mario menekan tombol P-Switch  yang menyebabkan semua arus  pipa pada Negeri Jamur berbalik arah, yakni pipa dengan arus dari kota $a$ ke kota $b$ berubah menjadi  pipa dengan arus dari kota $b$ ke kota $a$. Kemudian dimulai dari kota $P$, Mario berkelana ke kota-kota dengan menggunakan arus pada pipa-pipa tersebut.  Setelah efek P-Switch habis, semua arah arus pipa kembali seperti semula dan pada saat itu Mario sudah berada di kota $X$ dan telah mengunjungi semua kota tepat sekali dengan menggunakan tepat $n-1$ buah pipa,  sebutlah $n-1$ buah pipa yang telah dilalui Mario tersebut (beserta sebuah kanal dari $G$ ke $X$) sebagai pipa spesial, dan pipa yang lain sebagai pipa tak-spesial. 

Misalkan dimulai dari kota $X$, Mario akan menutup pipa-pipa pada Negeri Jamur dengan berkelana ke kota-kota melalui pipa-pipa tersebut dengan aturan berikut: 

• Apabila sebuah pipa telah dilalui oleh Mario, maka pipa tersebut langsung dia tutup dan tidak bisa dilalui lagi. 
• Pada setiap kota, Mario akan memilih keluar melalui pipa spesial hanya jika semua pipa tak-spesial yang menuju keluar dari kota tersebut sudah ditutup. 

Buktikan bahwa dengan aturan diatas, (apapun pilihan Mario) ketika Mario sudah tidak bisa berpindah kota, maka pada saat itu dia sedang berada kembali di kota $X$ dan telah menutup semua pipa pada Negeri Jamur.  

Solusi (Outline) :   Pertama-tama buktikan dulu ketika Mario stuck di suatu kota, yakni sudah tidak bisa kemana-mana lagi, maka pasti kota itu adalah kota $X$.  Jadi pipa spesial yang masuk dan keluar kota $X$ sudah dipakai.  Jika ada pipa yang belum dipakai, pilih pipa spesial $A$ ke $B$ yang belum terpakai dengan $B$ paling jauh ke $X$, maka nanti diperoleh pipa spesial dari $B$ juga belum terpakai, kontradiksi dengan $B$ paling jauh.


Yang jadi masalah adalah struktur pipa spesial pada soal, yang akhirnya kita ubah pada soal diatas menjadi cycle.

Berikut adalah beberapa versi soal :

1.  (Sebelum Ralat)  Struktur pipa spesial pada soal adalah directed path dari $X$ ke $G$ yang memuat semua kota.

2. (Setelah Ralat) Struktur pipa spesial pada soal adalah directed cycle yang memuat semua kota.

3. (Awal ketika buat) Struktur pipa spesial pada soal adalah directed path dari $G$ ke $X$ yang memuat semua kota.

Perhatikan bahwa yang membedakan  1 dan 3  itu hanya arah saja (mungkin dulu saya lupa bahwa ketika efek P-Switch habis, maka pipa spesialnya kembali ke arah semua juga.)

Versi 1 tidak berkerja karena ketika $B$ terjauh,  belum tentu ada pipa spesial bermula dari $B$.

Versi 3 harusnya tetap berkeja, namun ceritanya akan sedikit ribet, dan soal sekarang saja sudah panjang (Saya baru nyadar bahwa sebenarnya cukup bilang, pipa spesial ga balik lagi ke arah awal).

Ketika saya melihat kembali ketikan saya beberapa bulan lalu, ternyata saya menggunakan argument "$B$ paling dekat ke $X$" ,  sepertinya saya melakukan argument nya dengan asumsi bahwa pipa spesial arahnya tetap sama ketika P-Switch ditekan lagi.

Anyway, soal diatas merupakan adaptasi dari sebuah Algoritma untuk mendeteksi Eulerian Cycle pada sebuah graph simple, yang disebut Fleury's Algorithm. Algoritma yang saya tahu berkerja di Graph Simple, yaitu dengan melihat sebuah struktur subgraph berupa "bridge".  Nantinya edges yang berada pada bridge ini akan digunakan sebagai last resort ketika mencari Eulerian Cycle.

Saya mencoba mengerjakan Algoritma serupa ketika Graph yang diberikan adalah Graph berarah,  namun disini, agar terdapat Eulerian Cycle, saya beri kondisi in degree sama dengan out degree (yang ini saya jadiin soal Final ISMOC SMP :p ).

 Sayangnya meskipun dengan syarat in-degree dan out-degree, saya masih belum bisa menemukan struktur yang cocok untuk "bridge" di directed graph.  Setelah beberapa lama,  saya menggunakan argument ekstermal diatas, dan ambil asumsi malas bahwa bridge nya berbentuk garis saja. (yang akhirnya diubah menjadi cycle, karena phrase minim yang dibutuhkan).

Kira-kira struktur general subgraph spesial untuk Fleury's Algortihm versi directed graph ini apa ya?

Continue Reading

Masalah Cap-Set

Masalah Cap-Set

07:19:00   Cap Set,

Beberapa hari yang lalu, saya diberikan sebuah link oleh Pak Aleams Barra.   Pada link tersebut dijelaskan tentang sebuah masalah Kombinatorika yang baru-baru ini mendapat sebuah perkembangan berarti. Masalah ini biasa disebut sebagai cap set problem.  Masalah ini cukup high-profile karena beberapa matematikawan terkenal seperti Field Medalist Timothy Gowers dan Terrence Tao juga pernah tertarik dalam masalah ini.
Posting Blog Terrence Tao tahun 2007 tentang capset
Posting Blog Timothy Gowers tahun 2011 tentang capset

Dari hasil ini, dua konjektur langsung terbukti (dari post Prof. Gil Kalai) yaitu :

1. Erdos-Szemeredi Sunflower Conjecture dan 
2. Strong Cap Set Conjecture

Teorema 2.8 pada Paper Ini (oleh Noga Alon, Amir Shpilka, and Christopher Umans) 2 menyebabkan 1.  

Yang menghangatkan lagi diskusi tentang cap set baru-baru ini adalah ketika Ernie Croot, Vsevolod F. Lev, dan Péter P. Pach meletakkan paper pra-review mereka ke arxiv.org, tentang progression-free set di $\mathbb{Z}_4^n$ . Teknik Polynomial yang mereka pakai, menjadi game-changing dalam diskusi mengenai cap problem ini, sebelumnya para matematikawan menggunakan pendekatan Metode Fourier untuk memperoleh batas dari cap problem tersebut.  (Péter P. Pach ini ternyata pernah ikut IMO dua kali, dapat medali emas di tahun 2004)

Lemma polynomial (atau sekarang disebut Croot-Lev-Pach Lemma) sebenarnya sudah ditanyakan beberapa kali oleh Vsevolod Lev di mathoverflow (klik disini)  untuk melihat pertanyaaan Vsevolod Lev (dia sudah mencari jawabannya sampai tiga tahun!) (Vsevolod Lev ini ternyata proposer soal IMO 1989 no 6)

Argument yang dipakai oleh Croot-Lev-Pach, di adaptasi oleh matematikawan Jordan Ellenberg dan Dion Gijswijt untuk menyelesaikan masalah cap-set di $\mathbb{F}_q^n$. Setelah melihat Croot-Lev-Pach Lemma,  mereka berdua awalnya membuat paper yang terpisah  (sampai akhirnya mereka sadar bahwa argument mereka mirip) jadi mereka memutuskan untuk (akan) mempublish paper nya sebagai joint paper. (Ternyata si Jordan Ellenberg ini dulu tiga kali ikut IMO, dua kali perfect score 1987/1989 ) (Ternyata juga Dion Gijswijt ini pernah ikut IMO tiga kali, dua kali dapat HM , salah satunya di problem no 6 tahun 1994. )

Yang menarik adalah, argument yang dipakai pada paper diatas, cukup elementer sampai-sampai (seharusnya) mahasiswa matematika S1 bisa mengerti , yang tidak begitu elementer mungkin hanya pembatasan generalized binomial coefficient dengan ketaksamaan probabilistik, tapi jika sudah mengetahui variant-variant dari Ketaksamaan Probabilistic Tchebishev, harusnya tidak masalah.

Pada post-post ini saya akan mencoba (menjelaskan) argumen-argumen yang dipakai pada paper tersebut.   Anda bisa baca paper ini  yang katanya "cukup jelas".   Post-post berikut  ini sebenarnya hanyalah break-down argument dari paper tersebut (karena pak Barra bilang "mulai dari mana?" (breakdown-nya) ).  Saya rasa, yang sudah belajar sedikit tentang vektor space harusnya bisa mengikuti.

Post-post nya saya bagi menjadi 3 bagian: 

1.  Part I  (Ini menjelaskan masalah Cap Set, jika anda baca link di awal post ini, masalahnya dijelaskan oleh sebuah permainan kartu SET , disini saya mencoba menjelaskan mengapa bisa sampai nyasar ke vektor space)

2. Part II (Post ini cukup technical, saya mencoba menjelaskan beberapa pernyataan "satu baris" di paper tersebut yang sebenarnya jika di break-down mungkin 20 baris, tapi tetap elementer)

3. Part III (Karena part II kepanjangan, saya pisah, di Part II key lemma nya yaitu Croot-Lev-Pach Lemma sudah dibuktikan, disini kita pakai argument probabilistik untuk melakukan pembatasan (large deviation problem), saya  tidak buktikan ketaksamaannya karena itu bisa satu paper sendiri (saya paparkan paper nya di post part III )  )

Intinya jika anda mau baca paper nya langsung juga bisa, (cuma tiga halaman).

Continue Reading