April 30, 2016

Yet Another Proof of Brooke's Theorem

A classical result from Graph theory is that given \(G\) an undirected graph: \chi(G) \leq \Delta(G) + 1 Where \(\chi(G)\) is the minimum number of colors required to paint the nodes of \(G\) with the usual restriction that no node has the same color as any of its neighbors, and \(\Delta(G) = max_{v \in V(G)}(dg(v))\), that is, the maximum degree. This result is known as Brooke’s Theorem. The usual way to prove this result is to use the Greedy coloring algorithm: go through every node, and pick the lowest color not yet used by any of its neighbors. Read more

July 24, 2015

Characterizing the trace of a matrix

I have been studying for my finals lately, and so I decided to put together a proof of a nice exercise I found in some book. The trace function, given by \(tr : \mathbb{K}^{n \times n} \to \mathbb{K}\), is defined as tr(A) = \sum_{i=1}^n A_{ii} First of all, the proof of additivity \begin{equation} \begin{split} tr(A + B) &= \sum_{i=1}^n (A+B)_{ii} \\ &= \sum_{i=1}^n (A)_{ii} + (B)_{ii} \\ &= \sum_{i=1}^n (A)_{ii} + \sum_{i=1}^n (B)_{ii} \\ &= tr(A) + tr(B) \end{split} \end{equation} Afterwards, the proof of homogeneity Read more