MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 added 49 characters in body

[update] By an example of 4x4-matrices the ansatz below could not be used to solve the problem. The matrix $\small Q_K$ cannot in general be made lower triangular by choices of the $\small k_i$. I'll delete this answer soon if I cannot improve the ansatz.

I do not yet have a full answer but possibly a first step into one. I think that this can be answered unsing two facts:

a) There is a similarity transformation with a rotation T such that $\small P = T^{-1}\cdot A \cdot T = T' \cdot A \cdot T$ where P is triangular and has the eigenvalues of A on its diagonal.

b) Your sum-expression of vector outer products, let it be called matrix $\small E_K = \sum_{i=1}^n B_i k_i C_i = \sum_{i=1}^n k_i (B_i C_i)= \sum_{i=1}^n k_i E_i$ is a weighted (by the $\small k_i$ weights) sum of rank-1-matrices $\small E_i$

From the "similarity rotated version" of all matrices

$\qquad \small Q_K = T' E_K T = \sum_{i=1}^n k_i (T' E_i T) = \sum_{i=1}^n k_i Q_i$ (which should be made triangular by choices of $\small k_i$ ) and
$\qquad \small R = T' D T$ which is then also triangular

we get your final equation in its form with triangular matrices

$\qquad \small R = P + Q_K$

We'll have a solution if the weights $\small k_i$ for the rank-1non-triangular, generic but rank-1-matrices $\small Q_i$ can be chosen such that their sum $\small Q_K$ is becomes triangular and its diagonal equals the negative diagonal in $\small P$.

I've a vague speculation that the equation with this triangular matrices can easier be shown to be "almost always" possible, but have not yet a further concrete approach. At least this construction exhibits that the rank-1-matrices $\small E_i$ (and thus $\small Q_i$ ) cannot be simple scalar multiples of each other if A has full rank and thus the restriction to "for almost all" is unavoidable and possibly mainly consists of this property.

2 retract-announcement, ansatz was not sufficient; edited body

[update] By an example of 4x4-matrices the ansatz below could not be used to solve the problem. The matrix $\small Q_K$ cannot in general be made lower triangular by choices of the $\small k_i$. I'll delete this answer soon if I cannot improve the ansatz.

I do not yet have a full answer but possibly a first step into one. I think that this can be answered unsing two facts:

a) There is a similarity transformation with a rotation T such that $\small P = T^{-1}\cdot A \cdot T = T' \cdot A \cdot T$ where P is triangular and has the eigenvalues of A on its diagonal.

b) Your sum-expression of vector outer products, let it be called matrix $\small E_K = \sum_{i=1}^n B_i k_i C_i = \sum_{i=1}^n k_i (B_i C_i)= \sum_{i=1}^n k_i E_i$ is a weighted (by the $\small k_i$ weights) sum of rank-1-matrices $\small E_i$

From the "similarity rotated version" of all matrices

$\qquad \small Q_K = T' E_K T = \sum_{i=1}^n k_i (T' E_i T) = \sum_{i=1}^n k_i Q_i$ (which should be made triangular by choices of $\small k_i$ ) and
$\qquad \small R = T' D T$ which is then also triangular

we get your final equation in its form with triangular matrices

$\qquad \small R = P + Q_K$

We'll have a solution if the weights $\small k_i$ for the rank-1-matrices $\small Q_i$ can be chosen such that their sum $\small Q_K$ is triangular and its diagonal equals the negative diagonal in $\small P$.

I've a vague speculation that the equation with this triangular matrices can easier be shown to be "almost always" possible, but have not yet a further concrete approach. At least this construction exhibits that the rank-1-matrices $\small E_i$ (and thus $\small Q_i$ ) cannot be simple scalar multiples of each other if A has full rank and thus the restriction to "for almost all" is unavoidable and possibly mainly consists of this property.

1

I do not yet have a full answer but possibly a first step into one. I think that this can be answered unsing two facts:

a) There is a similarity transformation with a rotation T such that $\small P = T^{-1}\cdot A \cdot T = T' \cdot A \cdot T$ where P is triangular and has the eigenvalues of A on its diagonal.

b) Your sum-expression of vector outer products, let it be called matrix $\small E_K = \sum_{i=1}^n B_i k_i C_i = \sum_{i=1}^n k_i (B_i C_i)= \sum_{i=1}^n k_i E_i$ is a weighted (by the $\small k_i$ weights) sum of rank-1-matrices $\small E_i$

From the "similarity rotated version" of all matrices

$\qquad \small Q_K = T' E_K T = \sum_{i=1}^n k_i (T' E_i T) = \sum_{i=1}^n k_i Q_i$ (which should be made triangular by choices of $\small k_i$ ) and
$\qquad \small R = T' D T$ which is then also triangular

we get your final equation in its form with triangular matrices

$\qquad \small R = P + Q_K$

We'll have a solution if the weights $\small k_i$ for the rank-1-matrices $\small Q_i$ can be chosen such that their sum $\small Q_K$ is triangular and its diagonal equals the negative diagonal in $\small P$.

I've a vague speculation that the equation with this triangular matrices can easier be shown to be "almost always" possible, but have not yet a further concrete approach. At least this construction exhibits that the rank-1-matrices $\small E_i$ (and thus $\small Q_i$ ) cannot be simple scalar multiples of each other if A has full rank and thus the restriction to "for almost all" is unavoidable and possibly mainly consists of this property.