# determining linear independence given minimal polynomials

Suppose one has a set of numbers $S$, each of which is algebraic over a field $F$. Does knowing the minimal polynomial over $F$ of each element of $S$ help to determine whether $S$ is linearly independent over $F$?

The context is the case of a number $N=\sum_{i=1}^{n}a_i$ where I already know the minimal polynomial of each $a_i$, in a program I'm working on for calculating minimal polynomials. Let $d_i$ be the degree of the minimal polynomial of $a_i$, and $D=\prod_{i=1}^{n}d_i-1$. I start by calculating powers $1$ through $D$ of $N$ in its sum form, treating it as a multivariate polynomial with each $a_i$ a separate variable, and using the minimal polynomials of the $a_i$ to rewrite any terms whose degree with respect to $a_i$ is greater than or equal to $d_i$ as expressions of lower degree. This gives me $D$ polynomials with at most $D$ terms each, with the $k$th polynomial representing $N^k$. I treat the coefficients of the polynomials as a matrix, the $N^k$ its augmentation, and triangularize the matrix to find a linear combination of the $N^k$ that equals a constant. Subtracting the constant from the linear combination gives an annulling polynomial of $N$. I then factor this polynomial over the rationals and, for each of its factors, replace each $x^k$ with $N^k$ in its sum form in terms of the $a_i$ in order to see whether the factor is still annulling. I assume this last step can fail to detect that a factor is annulling in cases where the $a_i$ are linearly dependent, but detecting whether they are in general seems like a hard problem.

• For the simple question of "I have the polynomials in hand can I calculate this," the answer is yes. You have a matrix of coefficients $M\times [1~ x~ x^2~ \cdots ~ x^n]^T$ which equals a vector of your minimal polynomials. If this is linearly independent then the matrix of coefficients has an inverse. I only leave this as a comment because I am not 100% clear if this is actually your question. – law-of-fives Feb 13 '18 at 20:39
• @law-of-fives It sounds like it is the answer to my question. What are the coefficients in the matrix, exactly? – Alex Kindel Feb 13 '18 at 20:45
• @law-of-fives Oh wait, are they just the coefficients of the minimal polynomials? I suppose what wasn't obvious to me is that the minimal polynomials are linearly independent iff the numbers of which they are the minimal polynomials are too. – Alex Kindel Feb 13 '18 at 20:49
• your minimal polynomials are independent if they form a basis. If they form a basis, then we can transform from the standard polynomial basis to your custom basis. This amounts to what I described. I hope that helps! – law-of-fives Feb 13 '18 at 21:32
• @law-of-fives On second thought, it seems that linear dependence of the minimal polynomials of the elements of S doesn't imply linear dependence of the elements of S: the square roots of primes are all linearly independent from each other over the rationals, but since their minimal polynomials are each degree two, at most three of them can be linearly independent. – Alex Kindel Feb 14 '18 at 5:41