# Trying to sort the coefficients of the polynomial (z-a)(z-b)(z-c)…(z-n) into a vector

So I have a factored polynomial of the form (z-a)(z-b)(z-c)...(z-n) for n an even positive integer. Thus the coefficient of z^k for 0 <= k < n will be the sum of all distinct n-k element products taken from the set {a,b,...,n} multiplied by (-1)^k, I hope that makes sense, please ask if you need more clarification.

I'm trying to put these coefficients into a row vector with the first column containing the constant coefficient (which would be abc...n) and the last column containing the coefficient for z^n (which would be 1).

I imagine there is a way to brute force this with a ton of nested loops, but I'm hoping there is a more efficient way. This is being done in Matlab (which I'm not that familiar with) and I know Matlab has a ton of algorithms and functions, so maybe its got something I can use. Can anyone think of a way to do this?

Example: (z-1)(z-2)(z-3) = z^3 - (1 + 2 + 3)z^2 + (1*2 + 1*3 + 2*3)z - 1*2*3 = z^3 - 6z^2 + 11z - 6. Note that this example is n=3 odd, but n=4 would have taken too long to do by hand.

Edit: Let me know if you think this would be better posted at TCS or Math Stack Exchange.

-
Could you provide an example? – NoChance May 6 '12 at 23:31
Ok just added one. – Thoth May 6 '12 at 23:37
So the input is n=3, roots={1,2,3} and you want the output of {1,-6,11,-6}. If not correct please let me know. – NoChance May 6 '12 at 23:41
Ya for n=3 that's correct, above I was explaining how one derives these inputs for arbitrary n and arbitrary complex numbers. I also edited it above to include the alternating sign. – Thoth May 6 '12 at 23:45
I was a bit careless, the number of roots is an even positive integer which I foolishly also called n, but a,b,...,n are arbitrary complex numbers. Ok I'll take a look at that answer thanks. – Thoth May 6 '12 at 23:47

Have a look at the matlab routine poly.

``````>> poly([1,2,3])
ans =

1    -6    11    -6
``````

Or, to be more precise,

``````n = length(input);
c = [1 zeros(1,n)];
for j = 1:n
c(2:(j+1)) = c(2:(j+1)) - input(j).*c(1:j);
end
``````
-

if you have an array `{a,b,c,...,n}` then your starting result is `{1}`

you pop of the front (`a`) shift a copy of the subresult by 1 (add a 0 at the end) resulting in `{1,0}` and add the subresult with each element multiplies by `a` so the new subresult is {1,a}

do it again and you get `{1,a,0}+{b*1,a*b}={1,a+b,a*b}` again and you get `{1,a+b,a*b,0}+{c,c*(a+b),c*a*b}={1,a+b+c,a*c+b*c+a*b,c*a*b}` and so on...

-