Proving that Gaussian Naive Bayes Decision Boundary is Linear I need to come up with a Proof that Gaussian Naive Bayes has a linear decision boundary (In this case for Y={0,1})
I tried to work it out, but I am not able to pull out the xi term as it is stuck in the squared term

 A: Lets deal with the case that we have a new predictor value $x \in \mathbb{R}^p$. 
Then, we write the decision rule as 
$$ \delta(x) = \frac{P(Y = 1 \mid X=x)}{P(Y=0 \mid X = x)}.$$ If $\delta(x) > 1$, then $P(Y = 1 \mid X=x) > P(Y=0 \mid X = x)$, so our rule would predict the subject with predictors $x$ belongs to class $Y = 1$. Taking the log of both sides of our rule, 
$$ \log{\delta(x)} = \log P(Y = 1 \mid X=x) - \log P(Y=0 \mid X = x),$$
so $\log{\delta(x)} > 0$ is an equivalent rule. Then, recall: 
$$ P(Y=j \mid X = x) = \frac{P(X=x \mid Y=j) P(Y=j)}{P(X=x)},$$ so letting $\pi_j =  P(Y=j)$ for $j \in \left\{0, 1\right\}$, we have 
$$ \log{\delta(x)} = \log P(X=x \mid Y=0) + \pi_0 - \log P(X= x \mid Y=1) 
- \pi_1, $$
and the $\log P(X=x)$ cancel. Then, the Naive-Bayes model says that $$P(X=x \mid Y=j) \sim N_p(\mu_j, D)$$ where $D$ is a diagonal, symmetric and positive definite matrix for $j \in \left\{0, 1\right\}$. Thus, since $\log P(X=x \mid Y=j)$ is the multivariate normal log-likelihood for $j \in \left\{0, 1\right\}$, we have 
$$ \log{\delta(x)}  \propto  - (x - \mu_0)' D^{-1}(x - \mu_0)  + (x - \mu_1)' D^{-1}(x - \mu_1) + C,$$
where $C$ is a constant which does not depend on $x$. Expanding the quadratic terms, 
 $$ \log{\delta(x)}  \propto 
 - x'D^{-1} x + 2x' D^{-1} \mu_0 - \mu_0' D^{-1} \mu_0 + x'D^{-1}x  - 2 x D^{-1}\mu_1  + \mu_1' D^{-1} \mu_1  + C,$$
and the quadratic terms cancel, and the  $ -\mu_0 D^{-1} \mu_0'$ and $\mu_1 D^{-1} \mu_1$ are absorbed into the constant, so 
$$  \log{\delta(x)} \propto x'D^{-1}(\mu_0 - \mu_1) + \tilde{C}, $$
which is linear in $x$. 
A: The answer is based off Prof. Raquel Urtasun's lecture notes Slide 20-25. Punchline: Both the classes have to share the same co-variance matrix as the necessary condition.
Let, the decision boundary be $$ d(x) = \frac{P(Y = 1 \mid X=x)}{P(Y=0 \mid X = x)},$$ and we classify according to $d>1$ for class 1 and vice versa. Taking a log  on both sides we have $$\log{d(x)} = \log P(Y = 1 \mid X=x) - \log P(Y=0 \mid X = x).$$ Using Baye's rule, we can writre $$P(Y=j \mid X = x) = \frac{P(X=x \mid Y=j) P(Y=j)}{P(X=x)},$$ and denoting $\pi_j =  P(Y=j)$, i.e. likelihood of being classified into the $j^{th}$ class, we can expand $\log(d(x))$ as
$$\log{d(x)} = \log P(X=x \mid Y=0) + \pi_0 - \log P(X= x \mid Y=1) - \pi_1.$$
At this point we note that $$\log P(X=x \mid Y=0)  = -(x - \mu_0)' \Sigma_0^{-1}(x - \mu_0)$$ and $$\log P(X=x \mid Y=1)  = -(x - \mu_1)' \Sigma_1^{-1}(x - \mu_1).$$ Substituting both of these in the decision boundary equation we have:
$$\log{d(x)} = -(x - \mu_0)' \Sigma_0^{-1}(x - \mu_0) + \pi_0 + (x - \mu_1)' \Sigma_1^{-1}(x - \mu_1) - \pi_1$$
this can only simplify to a linear equation in $x$ iff the quadratic terms cancel i.e. $\Sigma_1 = \Sigma_0$, or else the decision boundary remains quadratic.
