  The problem of multiway partitioning of an undirected graph is considered. A
spectral method is used, where the k > 2 largest eigenvalues of the normalized
adjacency matrix (equivalently, the k smallest eigenvalues of the normalized
graph Laplacian) are computed. It is shown that the information necessary for
partitioning is contained in the subspace spanned by the k eigenvectors. The
partitioning is encoded in a matrix $\Psi$ in indicator form, which is computed
by approximating the eigenvector matrix by a product of $\Psi$ and an
orthogonal matrix. A measure of the distance of a graph to being
k-partitionable is defined, as well as two cut (cost) functions, for which
Cheeger inequalities are proved; thus the relation between the eigenvalue and
partitioning problems is established. Numerical examples are given that
demonstrate that the partitioning algorithm is efficient and robust.
