\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage[hypertex]{hyperref}
\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{mathrsfs}
\usepackage{cases}
\usepackage{array}
\renewcommand{\baselinestretch}{1.27}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
%\input setbmp
%\input{psfig.sty}
\usepackage{epsfig}
\newtheorem{defn}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{algorithm}{Algorithm}
\newtheorem{exercise}{Exercise}
%\usepackage[centertags]{amsmath}
\newcommand{\markex}{\nopagebreak\begin{center}\rule{5in}{.01in}\end{center}}
\newcommand{\markdefn}{\nopagebreak\hfill$\Diamond$}
\newcommand{\mb}{\mbox}
\newcommand{\bm}{\boldmath}
\def\b#1{\mb{\bm$#1$}}
\newfont{\Bb}{msbm10 scaled\magstep1}
\newfont{\Fr}{eufm10 scaled\magstep1}
\newfont{\Sc}{eusm10 scaled\magstep1}
%\pagestyle{empty}
\begin{document}
\noindent{\large ECE 602}\hfill{\Large Fall 2010}
\begin{center}
{\Large \bf Quadratic Forms and the Kronecker Product}\\
by\\
{\large Stanislaw H. \.{Z}ak}
\end{center}
\begin{center}
September 28, 2010
\end{center}
\medskip
%\bigskip
\begin{flushright}
%\parbox{5in}{Early amplifiers were made of crude materials that tended to disintegrate over use, causing the amp to ``run away.'' Not only would an aging relay amplify the phone signal, it would mistakenly compound any tiny deviation from the range it expected until the mushrooming error filled and killed the system. What was needed was Heron's {\it regula}, a counter signal to rein in the chief signal, to dampen the effect of the perpetual recycling. Black came up with a {\it negative} feedback loop, which was designated negative in contrast to the snowballing positive loop of the amplifier. Conceptually, the electrical negative feedback loop is a toilet flusher or thermostat. This braking circuit keeps the amplifier honed in on a steady amplification in the same way a thermostat hones in on a steady temperature. But instead of metallic levers, a weak train of electrons talks to itself.~\cite[page~116]{kelly94}}
\end{flushright}

\section*{Quadratic Forms}
%\addcontentsline{toc}{section}{Quadratic Forms}
%\label{sec:quadratform}
A real {\em quadratic form\/} is the product $\b x^{\top}\b Q\b x$, where $\b Q$ is a specified $n\times n$ matrix with real coefficients and $\b x$ is an $n\times 1$ real, column, vector. Without loss of generality, the matrix $\b Q$ can be taken to be symmetric, that is, $\b Q=\b Q^{\top}$. Indeed, if $\b Q$ is not symmetric, we can always replace it with a symmetric matrix without changing the quadratic form values. Indeed, because $z=\b x^{\top}\b Q\b x$ is a scalar, hence $z^{\top}=z$, and we have
\[
\left( \b x^{\top}\b Q\b x\right)^{\top}=\b x^{\top}\b Q^{\top}\b x=\b x^{\top}\b Q\b x.
\]
Therefore, we can write
\[
\b x^{\top}\b Q\b x=\b x^{\top}\left( \frac{1}{2}\b Q+\frac{1}{2}\b Q^{\top}\right)\b x=\b x^{\top}\left(\frac{\b Q+\b Q^{\top}}{2} \right)\b x,
\]
where $\frac{1}{2}\left(\b Q+\b Q^{\top} \right)$ is a symmetric matrix. Thus, the quadratic form values are unchanged if $\b Q$ is replaced with the symmetric matrix $\frac{1}{2}\left(\b Q+\b Q^{\top} \right)$. From now on, in our study of quadratic forms, we assume that $\b Q$ is symmetric.

A quadratic form $\b x^{\top}\b Q\b x$, or equivalently, the matrix $\b Q$, is called {\em positive semi-definite\/} if $\b x^{\top}\b Q\b x \ge 0$ for all $\b x$. It is {\em positive definite\/} if $\b x^{\top}\b Q\b x > 0$ for all $\b x\ne \b 0$. If $\b Q$ is positive semi-definite, then we write $\b Q\ge 0$, if it is positive definite, we write $\b Q>0$. We write $\b Q_1 \ge \b Q_2$ to mean that $\b Q_1-\b Q_2 \ge 0$. We say that $\b Q$ is {\em negative semi-definite\/} if $\b x^{\top}\b Q\b x \le 0$ for all $\b x$, it is {\em negative definite\/} if $\b x^{\top}\b Q\b x < 0$ for all $\b x \ne \b 0$. Note that $\b Q \le 0$ if and only if $-\b Q \ge 0$.

We now present tests for definiteness properties of symmetric matrices. We state these tests in terms of {\em principal minors\/} of a given real, symmetric, $n \times n$ matrix $\b Q$ with elements $q_{ij}$. We will also give tests for definiteness in terms of eigenvalues of $\b Q$. The principal minors of $\b Q$ are $\det \b Q$ itself and the determinants of submatrices of $\b Q$ obtained by removing successively an $i$-th row and $i$-th column. Specifically, for $p=1,2,\ldots,n$, the principal minors are
\[
\Delta_p\left(\begin{array}{cccc}
i_1, & i_2, &\ldots, & i_p\\
i_1, & i_2, &\ldots, & i_p
\end{array} \right)=\det\left[\begin{array}{cccc}
q_{i_1 i_1}&q_{i_1 i_2}&\cdots&q_{i_1 i_p}\\
q_{i_2 i_1}&q_{i_2 i_2}&\cdots&q_{i_2 i_p}\\
\vdots& \vdots & \ddots & \vdots\\
q_{i_p i_1}&q_{i_p i_2}&\cdots&q_{i_p i_p}
\end{array}\right]\quad 1 \le i_1 < i_2 < \cdots < i_p\le n.
\]
The above are called the principal minors of order $p$.

In the following, we use the fact that if $\b Q=\b Q^{\top}$, then its eigenvalues are all real.
\begin{thm}
\label{thm:testforpsd}
The following are equivalent:
\begin{itemize}
\item[(i)] The symmetric matrix $\b Q$ is positive semi-definite.
\item[(ii)] Principal minors of $\b Q$ are nonnegative, that is, for $p=1,2,\ldots,n$,
\[
\Delta_p\left(\begin{array}{cccc}
i_1, & i_2, &\ldots, & i_p\\
i_1, & i_2, &\ldots, & i_p
\end{array} \right) \ge 0, \quad 1 \le i_1 < i_2 < \cdots < i_p\le n.
\]
\item[(iii)] Eigenvalues of $\b Q$ are nonnegative,
\[
\lambda_i(\b Q) \ge 0,\quad i=1,2,\ldots,n.
\]
\end{itemize}
\end{thm}
We now give two tests for $\b Q=\b Q^{\top}$ to be positive definite; one in terms of its leading principal minors, and the other in terms of its eigenvalues. The {\em leading principal minors\/} of $\b Q$ are
\begin{eqnarray*}
&{}&\Delta_1\left(\begin{array}{c}
1\\
1
\end{array} \right)=q_{11},\quad \Delta_2\left(\begin{array}{cc}
1, & 2\\
1, & 2
\end{array} \right)=\det\left[\begin{array}{cc}
q_{11} & q_{12}\\
q_{21} & q_{22}
\end{array}\right],\\
&{}&\Delta_3\left(\begin{array}{ccc}
1,&2,&3\\
1,&2,&3
\end{array} \right)=\det\left[\begin{array}{ccc}
q_{11} & q_{12}& q_{13}\\
q_{21} & q_{22}& q_{23}\\
q_{31} & q_{32}& q_{33}
\end{array}\right],\ldots, \Delta_n\left(\begin{array}{cccc}
1, & 2, &\ldots, & n\\
1, & 2, &\ldots, & n
\end{array} \right)=\det \b Q.
\end{eqnarray*}
\begin{thm}
\label{thm:psosdeftests}
The following are equivalent:
\begin{itemize}
\item[(i)] The symmetric matrix $\b Q$ is positive definite.
\item[(ii)] Leading principal minors of $\b Q$ are positive, that is,
\[
\Delta_p\left(\begin{array}{cccc}
1, & 2, &\ldots, & p\\
1, & 2, &\ldots, & p
\end{array} \right) > 0, \quad p=1,2,\ldots,n.
\]
\item[(iii)] Eigenvalues of $\b Q$ are positive,
\[
\lambda_i(\b Q) > 0,\quad i=1,2,\ldots,n.
\]
\end{itemize}
\end{thm}

If a given matrix $\b Q\in \mb{\Bb R}^{n\times n}$ is symmetric, then its eigenvalues are all real and there exists a unitary matrix $\b U$ such that
\begin{equation}
\b U^{\top}\b Q\b U=\left[\begin{array}{cccc}
\lambda_1 & 0 & \cdots &0\\
0 & \lambda_2 &\cdots & 0\\
\vdots&{}&\ddots& \vdots\\
0 & 0& \cdots& \lambda_n
\end{array}\right]=\b{\Lambda}.
\label{eq:diaofsymauutr}
\end{equation}
Using the above, one can show that a symmetric positive semi-definite matrix $\b Q$ has a positive semi-definite symmetric square root, denoted $\b Q^{1/2}$ or $\sqrt{\b Q}$, that satisfies
\begin{equation}
\b Q^{1/2}\b Q^{1/2}=\b Q.
\label{eq:squmatrpro}
\end{equation}
Indeed, it follows from Theorem~\ref{thm:testforpsd} that if $\b Q=\b Q^{\top} \ge 0$ then its eigenvalues are all nonnegative. Hence,
\begin{equation}
\b{\Lambda}^{1/2}=\left[\begin{array}{cccc}
\lambda_1^{1/2} & 0 & \cdots &0\\
0 & \lambda_2^{1/2} &\cdots & 0\\
\vdots&{}&\ddots& \vdots\\
0 & 0& \cdots& \lambda_n^{1/2}
\end{array}\right]
\label{eq:sqroooflam}
\end{equation}
is well defined. Using the fact that $\b U^{\top}\b U=\b I_n$, we can define
\begin{equation}
\b Q^{1/2}=\b U\b{\Lambda}^{1/2}\b U^{\top},
\label{eq:deofsqroqpsd}
\end{equation}
which has the desired properties.

If $\b Q=\b Q^{\top}$ is positive semi-definite, and not positive definite, then some of its eigenvalues are equal to zero. Suppose that $\b Q$ has $r$ nonzero eigenvalues. Then, there is a unitary matrix, say $\b U$, such that
\begin{equation}
\b U^{\top}\b Q\b U=\left[\begin{array}{ccccccc}
\lambda_1 & 0 & \cdots&0&0 &\cdots&0\\
0 & \lambda_2 &\cdots&0&0 &\cdots& 0\\
\vdots&{}&\ddots& \vdots&{}&\ddots&\vdots\\
0 & 0& \cdots& \lambda_r&0&\cdots&0\\
0&0&\cdots&0&0&\cdots&0\\
\vdots&{}&{}&{}&{}&\ddots&\vdots\\
0&0&\cdots&0&0&\cdots&0
\end{array}\right].
\label{eq:diapsdmauum}
\end{equation}
Let $\b V\in \mb{\Bb R}^{n\times r}$ be a matrix that consists of the first $r$ columns of the matrix $\b U$, and let
\begin{equation}
\b C=\left[\begin{array}{cccc}
\lambda_1^{1/2} & 0 & \cdots &0\\
0 & \lambda_2^{1/2} &\cdots & 0\\
\vdots&{}&\ddots& \vdots\\
0 & 0& \cdots& \lambda_r^{1/2}
\end{array}\right]
\b V^{\top}.
\label{eq:srtmofpsd}
\end{equation}
Note that the matrix $\b C$ is of full rank. We have
\begin{equation}
\b Q=\b C^{\top}\b C.
\label{eq:furafaofq}
\end{equation}
We refer to~(\ref{eq:furafaofq}) as a full rank factorization of $\b Q$ because $\b C$ is of full rank.
%We can generalize the above, using~(\ref{eq:svddecompose}), to obtain a full rank factorization of a non-square matrix. Specifically, given an $m\times n$ matrix $\b A$ of rank $r$, we can represent it as
%\[
%\b A=\b B\b C,
%\]
%where $\b B$ is an $m\times r$ matrix and $\b C$ is a $r\times n$ matrix such that
%\[
%\mb{rank}(\b B)=\mb{rank}(\b C)=\mb{rank}(\b A)=r.
%\]

\section*{The Kronecker Product}
%\addcontentsline{toc}{section}{The Kronecker Product}\label{sec:kroneckerpro}
Let $\b A$ be an $m \times n$ and $\b B$ be a $p \times q$ matrices. The {\em Kronecker product\/} of $\b A$ and $\b B$, denoted $\b A \otimes \b B$, is an $mp \times nq$ matrix defined by
\begin{equation}
\b A \otimes \b B=\left[\begin{array}{cccc}
a_{11}\b B & a_{12} \b B&\cdots& a_{1n}\b B\\
a_{21}\b B & a_{22} \b B&\cdots& a_{2n}\b B\\
\vdots& \vdots & \ddots & \vdots\\
a_{m1}\b B & a_{m2} \b B&\cdots& a_{mn}\b B
\end{array}\right].
\label{eq:kronecker_def}
\end{equation}
Thus, the matrix $\b A \otimes \b B$ consists of $mn$ blocks. Using the definition of the Kronecker product, we can verify the following two properties:
\begin{eqnarray}
\left(\b A \otimes \b B\right)\left(\b C \otimes \b D \right) &=& \b A \b C \otimes \b B \b D,\\
\left(\b A \otimes \b B\right)^{\top} &=& \b A^{\top} \otimes \b B^{\top}.
\end{eqnarray}

Let
\[
\b X=\left[\begin{array}{cccc}
\b x_1,&\b x_2,&\ldots,&\b x_m
\end{array}\right]
\]
be a $n \times m$ matrix, where $\b x_i$, $i=1,2,\ldots,m$ are the columns of $\b X$. Each $\b x_i$ consists of $n$ elements. Then, the {\em vectorization operator\/} or {\em stacking operator\/} is defined as
\begin{eqnarray}
\mb{vec}(\b X) &=& \left[\begin{array}{cccc}
\b x^{\top}_1,&\b x^{\top}_2,&\ldots,&\b x^{\top}_m
\end{array}\right]^{\top}\nonumber\\
&=&\left[\begin{array}{ccccccccccccc}
x_{11}&x_{21}&\cdots&x_{n1}&x_{12}&x_{22}&\cdots&x_{n2}&\cdots&x_{1m}&x_{2m}&\cdots &x_{nm}
\end{array}\right]^{\top}
\end{eqnarray}
is the column $nm$-vector formed from the columns of $\b X$ taken in order. Let now $\b A$ be an $n\times n$, and $\b C$ and $\b X$ be $n\times m$ matrices. Then, the matrix equation
\begin{equation}
\b A \b X = \b C
\label{eq:axc_eq}
\end{equation}
can be written as
\begin{equation}
\left(\b I_m \otimes \b A \right) \mb{vec}(\b X)=\mb{vec}(\b C).
\end{equation}
Let $\b B$ be an $m \times m$ matrix, then the matrix equation
\begin{equation}
\b X \b B =\b C
\label{eq:xbc_eq}
\end{equation}
can be written as
\begin{equation}
\left(\b B^{\top} \otimes \b I_n \right) \mb{vec}(\b X)=\mb{vec}(\b C).
\end{equation}
Using the above two facts, we can verify that the Sylvester matrix equation,
\begin{equation}
\b A \b X + \b X \b B = \b C,
\label{eq:abc_eq}
\end{equation}
where $\b A$ is $n \times n$, $\b B$ is $m\times m$, and $\b C$ is $n\times m$, can be written as
\begin{equation}
\left( \b I_m \otimes \b A + \b B^{\top} \otimes \b I_n \right) \mb{vec}(\b X)=\mb{vec}(\b C).
\label{eq:abc_equieq}
\end{equation}

Let $\lambda_i$, $\b v_i$ be the eigenvalues and eigenvectors, respectively of $\b A$, and $\mu_j$ and $\b w_j$ the eigenvalues and eigenvectors of $m\times m$ matrix $\b B$. Then,
\begin{eqnarray}
\left( \b A \otimes \b B \right) \left(\b v_i \otimes \b w_j \right) &=& \b A \b v_i \otimes \b B \b w_j\nonumber\\
&=& \lambda _i \b v_i \otimes \mu _j \b w_j\nonumber\\
&=& \lambda _i \mu _j \left( \b v_i \otimes \b w_j \right).
\end{eqnarray}
Thus, the eigenvalues of $\b A \otimes \b B$ are $\lambda _i \mu_j$, and their respective eigenvectors are $\b v_i \otimes \b w_j$ for $i=1,2,\ldots ,n$, $j=1,2,\ldots ,m$.

We use the above result to study the matrix equation given by~(\ref{eq:abc_eq}). We represent~(\ref{eq:abc_eq}) as
\begin{equation}
\b M \,\mb{vec}(\b X)=\mb{vec}(\b C),
\label{eq:abc_asd}
\end{equation}
where
\begin{equation}
\b M = \b I_m \otimes \b A + \b B^{\top} \otimes \b I_n.
\end{equation}
The solution to~(\ref{eq:abc_asd}) is unique if, and only if, the $mn \times mn$ matrix $\b M$ is nonsingular. To find the condition for this to hold, consider the following matrix
\begin{equation}
\left(\b I_m + \varepsilon \b B^{\top} \right) \otimes \left( \b I_n + \varepsilon \b A \right)=\b I_m \otimes \b I_n + \varepsilon \b M + \varepsilon^2 \b B^{\top} \otimes \b A
\label{eq:long_matrix}
\end{equation}
whose eigenvalues are
\begin{equation}
\left(1+\varepsilon \mu_j\right) \left(1+\varepsilon \lambda_i \right) = 1+\varepsilon \left( \mu_j+\lambda_i \right) + \varepsilon^2 \mu_j \lambda_i
\label{eq:eigoflongm}
\end{equation}
because for a square matrix $\b Q$,
\[
\lambda_i \left(\b I_n + \varepsilon \b Q \right)=1+\varepsilon \lambda_i \left(\b Q \right).
\]
Comparing terms in $\varepsilon$ in~(\ref{eq:long_matrix}) and~(\ref{eq:eigoflongm}), we conclude that the eigenvalues of $\b M$ are $\lambda_i+\mu_j$, $i=1,2,\ldots ,n$, $j=1,2,\ldots ,m$. Hence, $\b M$ is nonsingular if and only if
\begin{equation}
\lambda_i+\mu_j \ne 0.
\end{equation}
The above is the necessary and sufficient condition for the solution $\b X$ of the matrix equation $\b A \b X + \b X \b B = \b C$ to be unique.

Another useful identity involving the Kronecker product is
\begin{equation}
\mb{vec}(\b A\b B\b C)=\left(\b C^{\top}\otimes \b A \right)\mb{vec}(\b B)
\label{eq:stack_three}
\end{equation}

For further information on the subject of the Kronecker product, we refer the reader to Brewer~\cite{brewer78}.

%\section{Summary and Notes}
%
%
%
%\section{Exercises}

%\begin{exercise}\label{ex:toiletsysex}\rm
%An example of a closed-loop feedback system is a toilet flushing device connected to a water tank. A toilet system is shown in Figure~\ref{fig:toiletd}. The control objective is to maintain the level of water in the tank at a constant level. Draw a block diagram of the system.
%\begin{figure}[h]
%\centering
%\includegraphics[scale=0.6]{TOILETD.eps}
%%\vspace{3.5in}
%%\hskip1in\special{bmp:c:/mybook/toiletd.bmp x=4.67in y=3.5in}
%\caption{Toilet-flushing system for Exercise~\ref{ex:toiletsysex}.}
%\label{fig:toiletd}
%\end{figure}
%\end{exercise}



\bibliography{root2}
\bibliographystyle{plain}
\end{document} 