Construct a companion matrix

Question

You have a number of polynomials who are lonely, so make them some companions (who won’t threaten to stab)!

For a polynomial of degree n, there is an n by n companion cube matrix for it. You need to make a function that accepts a list of coefficients for a polynomial in either ascending (a + bx +cx^2 + …) or descending (ax^n + bx^(n-1) + cx^(n-2)+…) order (but not both) and output the companion matrix.

for a polynomial c0 + c1x + c2x^2 + ... + cn-1x^(n-1) + x^n, its companion matrix is

     (0, 0, 0, ..., -c0  ),
     (1, 0, 0, ..., -c1  ),
     (0, 1, 0, ..., -c2  ),
     (...................),
     (0, 0, ..., 1, -cn-1)

note that the coefficient for x^n is 1. For any other value, divide all the rest of the coefficients by x^n's. Additionally, the 1's are offset from the diagonal.

If the language you’re using already contains a function or module that does this, you can’t use it – you must write your own.

For instance, if you had 4x^2 – 7x + 12, the coefficients in ascending order are (12, -7, 4) and descending order (4, -7, 12). The function or program should output [(0, -3.0), (1, 1.75)] for either order. Specify which order your code accepts. Minimum polynomial should be a quadratic. Coefficients are restricted to real numbers.

Below are examples – your output does not have to match the pretty formatting but it should output the rows (in the ()) of the matrix in order.

Ascending order:

input:
    [3., 7., -5., 4., 1.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [-4., -7., 13.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [23., 1., 92., 8., -45., 88., 88.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

Descending order:

input:
    [1., 4., -5., 7., 3.]
output:
    [(0, 0, 0, -3.),
     (1, 0, 0, -7.),
     (0, 1, 0,  5.),
     (0, 0, 1, -4.)]

input:
    [13., -7., -4.]
output:
    [(0, 0.30769231),
     (1, 0.53846154)]

input:
    [88., 88., -45., 8., 92.,1., 23.]
output:
    [(0, 0, 0, 0, 0, -0.26136364),
     (1, 0, 0, 0, 0, -0.01136364),
     (0, 1, 0, 0, 0, -1.04545455),
     (0, 0, 1, 0, 0, -0.09090909),
     (0, 0, 0, 1, 0,  0.51136364),
     (0, 0, 0, 0, 1, -1.        )]

---

Dennis wins with 20 bytes!

Answer 1

CJam, 23 20 bytes

{)W*f/_,,_ff=1f>\.+}

This is a function that pops the input (ascending order) from the stack and pushes the output in return.

Try it online in the CJam interpreter.

How it works

)   e# Pop the last element from the input array.
W*  e# Multiply it by -1.
f/  e# Divide the remaining array elements by this product.
_,  e# Push a copy of the array and compute its length (L).
,_  e# Push [0 ... L-1] twice.
ff= e# For each I in [0 ... L-1]:
    e#   For each J in [0 ... L-1]:
    e#     Push (I==J).
    e# This pushes the L x L identity matrix.
1f> e# Discard the first element of each row, i.e., the first column.
\   e# Swap the result with the modified input.
.+  e# Vectorized append; append the input as a new column.

Answer 2

CJam, 32 31 28 bytes

0q~)f/f-_,(_,\0a*1+fm<~]W%z

Try it online

This takes the input in ascending order, using the CJam list format. Sample input:

[-4.0 -7.0 13.0]

Explanation:

0     Push a 0 for later sign inversion.
q~    Get and interpret input.
)     Pop off last value.
f/    Divide all other values by it.
f-    Invert sign of values.
_,    Get count of values, which corresponds to n.
(     Decrement by 1.
_,    Create list of offsets [0 1 ... n-1] for later.
\     Swap n-1 back to top.
0a*   Create list of n-1 zeros.
1+    Append a 1. This is the second-but-last column [0 0 ... 0 1].
fm<   Apply rotation with all offsets [0 1 ... n-1] to column.
~     Unwrap the list of 0/1 columns.
]     Wrap all columns
W%    Invert their order from last-to-first to first-to last.
z     Transpose to get final matrix.
`     Convert to string for output.

Answer 3

APL, 40 30 bytes

{(-n↑⍵÷⊃⊖⍵),⍨⍉1↓⍉∘.=⍨⍳n←1-⍨≢⍵}

Accepts input in ascending order.

Explanation:

{
                        n←1-⍨≢⍵    ⍝ Define n = length(input)-1
                   ∘.=⍨⍳           ⍝ Create an n×n identity matrix
               ⍉1↓⍉                ⍝ Drop the leftmost column
            ,⍨                     ⍝ Append on the right:
  (-n↑⍵                            ⍝ n negated coefficients,
       ÷⊃⊖⍵)                       ⍝ divided by the n+1st
}

Try it online

Answer 4

Julia, 43 bytes

c->rot180([-c[2:(n=end)]/c[] eye(n-1,n-2)])

This uses descending order for the input. It constructs the matrix rotated 180 degrees, in order to enable more efficient use of "eye", then rotates the matrix into the right orientation.

Answer 5

Julia, 64 44 bytes

c->(k=c[n=end];[eye(n-=1)[:,2:n] -c[1:n]/k])

Accepts a vector of the coefficients in ascending order.

Ungolfed:

function f(c::Array)
    # Simultaneously define k = the last element of c and
    # n = the length of c
    k = c[n = end]

    # Decrement n, create an n×n identity matrix, and exclude the
    # first column. Horizontally append the negated coefficients.
    [eye(n-=1)[:,2:n] -c[1:n]/k]
end

Try it online

Saved 20 bytes thanks to Glen O!

Answer 6

R, 71 59 bytes

Takes input in ascending order.

function(x)cbind(diag(n<-length(x)-1)[,2:n],-x[1:n]/x[n+1])

Ungolfed:

f <- function(x) {
    # Get the length of the input
    n <- length(x)-1

    # Create an identity matrix and exclude the first column
    i <- diag(n)[, 2:n]

    # Horizontally append the negated coefficients divided
    # by the last one
    cbind(i, -x[1:n]/x[n+1])
}

Answer 7

Matlab, 66 bytes

function y=f(c)
n=numel(c);y=[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)];

It uses ascending order for the input, with format [3., 7., -5., 4., 1.] or [3. 7. -5. 4. 1.].

Try it online (in Octave).

Example (in Matlab):

>> f([23., 1., 92., 8., -45., 88., 88.])
ans =
                   0                   0                   0                   0                   0  -0.261363636363636
   1.000000000000000                   0                   0                   0                   0  -0.011363636363636
                   0   1.000000000000000                   0                   0                   0  -1.045454545454545
                   0                   0   1.000000000000000                   0                   0  -0.090909090909091
                   0                   0                   0   1.000000000000000                   0   0.511363636363636
                   0                   0                   0                   0   1.000000000000000  -1.000000000000000

---

If a program is valid (instead of a function), with stdin and stdout:

Matlab, 59 bytes

c=input('');n=numel(c);[[0*(3:n);eye(n-2)] -c(1:n-1)'/c(n)]

Answer 8

Octave, 45 44 bytes

Assuming c is a column vector with the coefficient of the highest power of x at the end.

@(c)[eye(n=rows(c)-1)(:,2:n),-c(1:n)/c(end)]

Old version:

@(c)[eye(n=numel(c)-1)(:,2:n),-c(1:n)/c(end)]

_{High five, Julia!}

Answer 9

Python 2, 141 bytes

My own attempt:

def C(p):
 c,r=p.pop(0),range;d=[-i/c for i in p];n=len(d);m=[[0]*n for i in r(n)]
 for i in r(n-1):m[i][i+1]=1
 m[-1]=d[::-1];return zip(*m)

Takes a list of the coefficients in descending order and first builds the transpose of the companion matrix - known for stabbing and being talkative. The return uses zip to produce the transpose of this transpose to get the actual matrix.

>>> C([1., 4., -5., 7., 3.])
[(0, 0, 0, -3.0), (1, 0, 0, -7.0), (0, 1, 0, 5.0), (0, 0, 1, -4.0)]

Answer 10

JavaScript (ES6) 85

Ascending order.

Test running the snippet below in any EcmaScript 6 compliant browser.

f=c=>alert(c.map((v,i)=>c.map((x,j)=>++j-i?j-c.length?0:-v/m:1),m=c.pop()).join(`
`))

// test
// redefine alert to write into the snippet body
alert=x=>O.innerHTML+=x+'\n'

function test() {
  v=I.value.match(/\d+/g)
  I.value=v+''
  alert(v)
  f(v)
}  

test()

<input value='23.,1.,92.,8.,-45.,88.,88.' id=I><button onclick="test()">-></button>
<pre id=O></pre>

Answer 11

Pari/GP, 49 bytes

p->concat(matid(#p-1),-p[1..#p-1]~/p[#p])[,2..#p]

Try it online!

Answer 12

TI-BASIC, 50 bytes

Ans→X
List▶matr(ΔList(Ans-cumSum(Ans)),[A]
dim(Ans
augment(augment(0randM(Ans-2,1),identity(Ans-2))ᵀ,[A]∟X(Ans)⁻¹

Takes input in ascending order. Note that this will not work for polynomials of degree <2, because TI-BASIC does not support empty matrices or lists. Pending a ruling from OP, I can fix this at the cost of a few bytes.

First, we store the list into ∟X to use the last element later; then, we calculate ΔList(Ans-cumSum(Ans)), which is just the negated list with the last element chopped off, and convert it to a column vector. Since List▶matr( doesn't modify Ans, we can use the next line to take the dimension of the list, which we use thrice. TI-BASIC doesn't have vertical concatenation, so we need to take transposes and horizontally concatenate. In the last line, [A]/∟X(Ans wouldn't work because matrices can be multiplied by scalars but not divided.

An aside: To generate the row vector of zeros, we take advantage of the rarely useful randM( command. randM( creates a random matrix, but its entries are always random integers between -9 and 9 (!), so it's really only useful to create zero matrices.