Why is Matrix A in Metric Learning expected to be PSD? I read that in Metric learning the metric A is supposed to PSD due to the non-negativity constraint on the distance. 
My question is how does A being a PSD (positive semi-definite) ensures that the distance(Mahalanobis) will be non-negative?
 A: I'm assuming you mean the following distance:
$$
d^2(x, y) = (x - y)^T A (x - y)
.$$
Say $A$ is $n \times n$.
Recall that one definition of a positive definite matrix is that it's a symmetric matrix such that for any nonzero vector $u \in \mathbb R^n$, $u^T A u > 0$.
Now, for $d$ to be a distance metric we require $d(x, y) > 0$ for any $x \ne y$. In that case, $x - y \ne 0$, and since $A$ is positive definite, $d(x, y) = \sqrt{(x - y)^T A (x - y)} > 0$.
If you prefer the definition that all eigenvalues are positive, we can prove that this property also holds from that: letting $v_i$ be the $i$th eigenvector and $\lambda_i$ its corresponding eigenvalue, we can write $u = \sum_{i=1}^n \alpha_i v_i$ since the $v_i$ are an orthonormal basis, so that
\begin{align}
u^T (A u)
&= \left( \sum_{i=1}^n \alpha_i v_i \right)^T \left( \sum_{i=1}^n \alpha_i A v_i \right)
\\&= \left( \sum_{i=1}^n \alpha_i v_i \right)^T \left( \sum_{i=1}^n \alpha_i \lambda_i v_i \right)
\\&= \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j \lambda_i v_i^T v_j
\\&= \sum_{i=1}^n \alpha_i^2 \lambda_i > 0
\end{align}
since $v_i^T v_j = \begin{cases} 1 & i = j \\ 0 & i \ne j \end{cases}$, $\lambda_i > 0$, and at least one $\alpha_i \ne 0$ since $u \ne 0$.
The other requirements are also always satisfied. The only one that's tricky is the triangle inequality, but note that if $A$ is positive semidefinite (including if it's positive definite), there is some $R$ such that $A = R^T R$. But then $(x - y)^T R^T R (x - y) = (R x - R y)^T (R x - R y)$, so $d$ is the Euclidean distance between the points $R x$ and $R y$ – thus the triangle inequality holds.
This also gives some insight on the difference between psd and pd matrices $A$. If $A$ is pd, then any valid $R$ above is of full rank, and the points $R x$ are in an $n$ dimensional space; $d$, which is the Euclidean metric in that space, is thus a valid metric. If $A$ is psd with $m < n$ nonzero eigenvalues, then $R$ is of rank $m$, and so necessarily some distinct points in $\mathbb R^n$ are mapped to the same point in the $m$-dimensional range of $R$: there are some $x$ and $y$ such that $R x = R y$. But then $d(x, y) = 0$, making it not a valid metric. All the other properties hold, though, so that $d$ is then a pseudometric.
