Why is the matrix-defined Cross Product of two 3D vectors always orthogonal? By matrix-defined, I mean

$$\left&lt;a,b,c\right&gt;\times\left&lt;d,e,f\right&gt; = \left| 

\begin{array}{ccc}
i &amp; j &amp; k\\
a &amp; b &amp; c\\
d &amp; e &amp; f
\end{array}

\right|$$

...instead of the definition of the product of the magnitudes multiplied by the sign of their angle, in the direction orthogonal)

If I try cross producting two vectors with no $k$ component, I get one with only $k$, which is expected. But why?

As has been pointed out, I am asking why the algebraic definition lines up with the geometric definition.
Here's an explanation in terms of the Hodge dual and the exterior (wedge) product.

Let ${e_1, e_2, e_3}$ be the standard orthonormal basis for $\mathbb{R}^3$. Consider the two vectors $a = a_1 e_1 + a_2 e_2 + a_3 e_3$ and $b = b_1 e_1 + b_2 e_2 + b_3 e_3$. From the matrix computation we obtain the familiar formula

$a\times b = (a_2 b_3 - a_3 b_2) e_1 + (a_3 b_1 - a_1 b_3) e_2 + (a_1 b_2 - a_2 b_1) e_3$.

But (see note at the bottom)

$a \wedge b = (a_1 b_2 - a_2 b_1) e_1 \wedge e_2 + (a_2 b_3 - a_3 b_2) e_2 \wedge e_3 + (a_3 b_1 - a_1 b_3) e_3 \wedge e_1$,

where the wedge $\wedge$ represents the exterior product. One can now compute the dual of this latter expression using that the left contraction of $(e_1 \wedge e_2)$ onto $(e_3 \wedge e_2 \wedge e_1)$ is $e_3$ (and similar relations). The result is that

$a \times b = (a \wedge b)^*$,

that is, the cross product of $a$ and $b$ is the dual of their exterior product.

Geometrically, this is an incredible picture. The exterior product is the plane element spanned by both $a$ and $b$, and the dual is the vector orthogonal to that plane.

This is my favorite interpretation of the cross product, but it's only helpful, of course, if you're familiar with exterior algebra and the Hodge dual.

Note: The wedge product can be found by formally computing 

$(a_1 e_1 + a_2 e_2 + a_3 e_3) \wedge (b_1 e_1 + b_2 e_2 + b_3 e_3)$

using the distributivity and anticommutation relations of the exterior product.
The obvious but slightly trite answer is "because that's just how the cross-product works as an operation".

If you're looking for an intuitive reason, the cross-product by definition produces a vector that is orthogonal to the two operand (input) vectors. You know that the base vectors $\mathbf{i}$, $\mathbf{j}$, and $\mathbf{k}$ are all orthogonal, thus if your two input vectors lie on the $(x, y)$ plane (i.e. only $\mathbf{i}$ and $\mathbf{j}$ components), you know that any orthogonal vector must have only a component in the $z$ direction (multiple of $\mathbf{k}$).