How to solve for the minimum KL Divergence when the distribution is discrete? Say we have a simple case of $p(x,y)$ is a 3x3 matrix:
$$\begin{bmatrix} 
 1/6       & 0 & 0 \\
    1/6       & 3/6 & 0  \\
    0       & 0 & 1/6  
\end{bmatrix}$$
And $q(x,y)=q(x)q(y)$.  If I'm trying to solve for the form of $q_x$ and $q_y$ that minimizes $D_{KL}(q||p)$, what's the best approach to solving this problem?  I know that if the two distributions were continuous, I could use gradient descent or something similar, but without trying to brute force the solution here, I can't see the proper way to solve.
Lastly, I've been concerned about taking the $D_{KL}(q||p)$ when the two distributions do not have the same support (because of the 0's in the matrix above), but I read somewhere on SE that we can treat those $\log(0)$ terms as 0 although I remain unconvinced.
 A: Your problem is about handling impossible events in KL-divergence. Your $x$ and $y$ notation is not useful here (though it might be relevant for your specific problem). We can flatten everything and call X = (x,y). 
Let's start from the definition of KL divergence : 
$$D_{KL}(q\|p) = \sum _{X} q(X) \log\left(\frac{q(X)}{p(X)}\right)$$
It looks rather undefined as soon $p(X)=0$ or $q(X)=0$... Let's look at the calculus : 
Case 1: $q(X) = 0$ and $p(X)\neq 0$ : In that case , $\lim_{x\rightarrow 0}xlog(x) =0$. Hence, we will count 0 in the sum.
Case 2: $q(X) \neq 0$ and $p(X) = 0$ : In that case , $\lim_{x\rightarrow 0}log(1/x) =+ \infty$. Hence, we will count $+ \infty$ in the sum.
Case 3: $q(X) =0$ and $p(X) = 0$ : Then, it is really undefined...
Now, let's look at some higher level interpretation. $D_{KL}(q\|p)$ quantifies how credible distribution $p$ is when we sample according to $q$.
Case 1: $q(X) = 0$ and $p(X)\neq 0$ : Since we sample according to $q$, we will never sample event $X$. Hence, it does not weight in $D_{KL}(q\|p)$.
Case 2: $q(X) \neq 0$ and $p(X) = 0$ : Since we sample according to $q$, a single sample of event $X$ tells us with absolute certainty that we are not sampling $p$. Hence, $D_{KL}(q\|p)$ is infinite.
Case 3: $q(X) =0$ and $p(X) = 0$ : $X$ is an event which does not happen in $p$ and $q$. So why would you put it in the sum in the first place? 
For your specific case, you have a lot of $0$ in $p$. Hence, your KL-divergence will be infinite except if $q$ have the same zeros. Since you further assume that $q(x,y) = q_x(x)q_y(y)$, we have the following constraint : 
$$q_x(1)q_y(2)=0$$
$$q_x(1)q_y(3)=0$$
$$q_x(2)q_y(3)=0$$
$$q_x(3)q_y(1)=0$$
$$q_x(3)q_y(2)=0$$
For instance :
$q_x = \left[1/2, 1/2, 0 \right]$ and 
$q_y = \left[1, 0, 0 \right]$.
