### Abstract:

Linear pencils are algebraic structures defined by linear polynomials in several real variables,whose coefficients are hermitian matrices. Alternatively, they may be viewed as matrices whose entries are linear polynomials in the variables in question. By requiring that the matrix thus defined be positive semidefinite, that is having no negative eigenvalues, a convex region called a spectrahedron is defined in the space of variables.Spectrahedra and linear pencils are the subject of a field of study known as semidefinite programming, which has wide application in quantitative science, in such fields as control theory, computational finance, signal processing, and fluid dynamics, among many others. The particular focus of this work is a fundamental problem in matrix theory, known as Kippenhahn's Conjecture. It was formulated in 1951 by Rudolf Kippenhahn. The conjecture concerns two-variable linear pencils, say in variables x and y with hermitian matrix coefficients H and K respectively. The conjecture relates the eigenvalues of the linear pencil, and the matrix algebra generated by H and K. The claim is that if H and K generate the full matrix algebra, then there must be some x and y such that at least one of the eigenvalues of xH + yK is simple. The conjecture is known to be true for matrices of order less than 8, but it is false in general. It was disproven in 1983 by Laffey, who presented a single counterexample of 8 x 8 matrices. We have extended the understanding of Kippenhahn's Conjecture by constructing two new one-parameter families of counterexamples, and proving a general theorem which allows for the construction of additional such families. Among the techniques we have used are graph theory and matrix theory. Recently there has been much work on linear pencils in the fields of free analysis and non-commutative algebra. This involves replacing the commutative real variables with hermitian matrices which may be of any dimension, a process often referred to as quantisation. A quantum version of Kippenhahn's Conjecture, known as the Quantum Kippenhahn Theorem, has recently been proven by Klep and Volcic: if H and K generate the full matrix algebra, then there must be some X and Y such that X⊕H + Y⊕K has at least one simple eigenvalue. However, the theorem was not constructive. We have succeeded in constructing X and Y of the smallest possible size for both families of new counterexamples to the Kippenhahn Conjecture, and for the already known counterexample.