<p><a href="https://doi.org/10.1007/978-3-662-03338-8_14" rel="noreferrer">Bürgisser-Clausen-Shokrollahi, the beginning of Chapter 14</a>. Specifically Strassen's Prop 14.1, through equation (14.8).</p>

CC BY-SA 4.0
2024-11-18T16:48:59.333Z
2024-11-18T16:48:59.333Z
Joshua Grochow
<p>In Ran Raz's <a href="https://eccc.weizmann.ac.il/report/2002/012" rel="noreferrer">paper</a>, top of page 3, he uses the following claim without proof or reference, saying it is well-known and easy to prove:
Let <span class="math-container">$C$</span> be an arithmetic circuit for multiplying two matrices over the reals (or any other bi-linear function).
Then we can transform <span class="math-container">$C$</span> into a circuit <span class="math-container">$C'$</span> for multiplying two matrices such that</p>
<ul>
<li><span class="math-container">$C'$</span> is larger than <span class="math-container">$C$</span> by at most a universal constant factor.</li>
<li>Every multiplication gate in <span class="math-container">$C'$</span> is bi-linear: meaning it computes a product of a linear combination of the first matrix's values, with a linear combination of the second matrix's values.</li>
</ul>
<p>Can someone write a proof or give a reference?</p>

<lower-bounds>
Circuits for matrix multiplication over reals can be assumed bi-linear? Looking for reference/proof
relG
# Circuits for matrix multiplication over reals can be assumed bi-linear? Looking for reference/proof

(Asked by: username_0 on 2024-11-18)

In Ran Raz's [paper](https://eccc.weizmann.ac.il/report/2002/012), top of page 3, he uses the following claim without proof or reference, saying it is well-known and easy to prove:
Let $C$ be an arithmetic circuit for multiplying two matrices over the reals (or any other bi-linear function).
Then we can transform $C$ into a circuit $C'$ for multiplying two matrices such that

* $C'$ is larger than $C$ by at most a universal constant factor.
* Every multiplication gate in $C'$ is bi-linear: meaning it computes a product of a linear combination of the first matrix's values, with a linear combination of the second matrix's values.

Can someone write a proof or give a reference?

**Tags:** lower-bounds

---

## 1 answers

### Answer by username_1 on 2024-11-18. Score: 9

[Bürgisser-Clausen-Shokrollahi, the beginning of Chapter 14](https://doi.org/10.1007/978-3-662-03338-8_14). Specifically Strassen's Prop 14.1, through equation (14.8).


---

