Generation of "random" multilinear polynomials for testing non-negativity algorithm

Question

Multilinear polynomial is a multivariate polynomial where the exponent is zero or one. My instructor suggests to test my non-negativity algorithm with "random multilinear functions" which I call at the best red herring unless specifying the meaning of "random". Suppose you need to test your algorithm working with multilinear functions.

On which kind of "random" polynomials should a non-negativity algorithm be tested against?

Answer 1

Multilinear polynomials are in a 1-1 correspondence with linear maps into $\mathbb{R}$, specifically

$$\sum_{i_m \in\{0,1\}} a_{i_1 \cdots i_n} x^{i_1} \cdots x^{i_n}$$

is isomorphic to a linear map $\mathbb{R}^{2^n} \to \mathbb{R}$, which can be specified with $2^n$ numbers. So you could generate a random linear map by generating $2^n$ random numbers, and map that to a multilinear polynomial.

---

Edit Here's an example of how to reproducably generate random numbers in Matlab:

>> seed = 147835;
>> rng(seed);      % Set initial seed
>> x = rand(5, 1); % Generate random numbers
>> rng(seed);      % Reset the seed
>> y = rand(5, 1); % Generate new random numbers
>> disp([x, y])
    0.1171    0.1171
    0.6895    0.6895
    0.8330    0.8330
    0.4596    0.4596
    0.8468    0.8468

Note that the same random numbers are generated each time.