<p>"<em>Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science?"</em></p>

<p>Here is a partial answer in my mind:
I think it is because nature is abound with objects/phenomena - representable by functions which albeit being nonlinear on their operands, are actually members of linear spaces. The wave functions in a Hilbert space, the components in a fourier spectrum, polynomial rings, stochastic processes - they all behave in that fashion. 
Even very general definitions of curved spaces are built out of composing small charts of flat spaces ( manifolds, Riemann surfaces, .. ). 
Moreover, nature is full of symmetries and studying symmetries invariably gets into study of linear operators (representation theory, in my mind, is creeping into many areas of computer science ever so ubiquitously).</p>

<p>These are in addition to the cases where the operators themselves are linear in nature. </p>

<p>A large fraction of problems for which we need computer programs, arise either directly as, or are abstracted from, naturally occuring phenomena. Perhaps studying/solving linear systems shouldn't be a great deal of surprise, after all?</p>

CC BY-SA 3.0
2012-10-19T00:08:32.967Z
Ah yes, the wonderful joys of lifting maps.
Suresh Venkat
CC BY-SA 3.0
2012-10-18T22:15:50.947Z
2012-10-18T22:28:15.417Z
2012-10-18T22:28:15.417Z
Arnab
<p>I think all answers here are pretty good and linear systems admitting tractable solutions is definitely a big factor. I also like Arnab's answer about the ubiquity of linear spaces. But I also feel the need to point out that the instinct to ask this question is certainly not misplaced. Since the question employed some physical intuition, I think some physics context might be useful to illustrate why this is actually a really good question and why there's a slight caveat to the answers.</p>
<p>It is after all true that one of the big reasons why we think quantum mechanics is incomplete, is precisely because the Schrödinger equation, which governs quantum dynamics, is linear. Linear systems do not admit chaos, non-linear systems do. So it would seem that a purely quantum mechanical universe is one that is void of chaos, which doesn't correspond to our universe (quantum chaos is an open question in physics). This has implications for the question of whether quantum computers can be hoped to truly simulate as much as some hope them to, since quantum computers can be thought of as efficient in simulating nature because we don't have to simulate the &quot;quantumness&quot; (this is a bit of an oversimplification, but true to a certain extent).</p>
<p>Even if we look at machine learning, it seems to be the case that non-linear neural nets are needed to be particularly good at learning. Linear systems simply don't do as well here.</p>
<p>So while most of our universe seems perfectly well described by approximations of linearity, it may just very well be that we're missing out on <em>some</em> structure by not being better at computing non-linear systems.</p>

CC BY-SA 4.0
2022-07-07T23:35:34.840Z
2022-07-07T23:35:34.840Z
Daniel Primosch
<p>The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability. </p>

<p>Perhaps what is more relevant is "why do linear systems admit tractable solutions ?" which is not exactly what you asked, but is related. One perspective on this is composability. Since the defining property of a linear system is that $f(x + y) = f(x) + f(y)$, this imparts a kind of "memorylessness" to the system. To build up a solution to a problem I can focus on individual pieces and combine them with no penalty. Indeed, the premise of most algorithms for flow is precisely that. </p>

<p>This memorylessness imparts efficiency: I can break things into pieces, or work iteratively, and I don't lose by virtue of doing so. I can still make bad decisions (c.f. greedy algorithms) but the act of splitting things up itself doesn't hurt me. </p>

<p>This is one reason why linearity has such power. There are probably many others. </p>

CC BY-SA 3.0
2012-10-28T00:31:34.033Z
I like this answer but to those that argue that linear programming is not the boundary, I respond with: "it's P-complete!" ;).
Artem Kaznatcheev
CC BY-SA 3.0
2012-10-28T05:53:34.573Z
Yes but is it the case that (for example) SDPs are not ?
Suresh Venkat
CC BY-SA 3.0
2012-10-28T07:20:41.537Z
We don't have to have a single boundary, and some boundaries of P (say quadratic programming with positive semi-definite matrix for the squared terms) do seem more general. I didn't mean to disagree, was just pointing out that the boundary is more a matter of taste when picking between P-complete problems.
Artem Kaznatcheev
CC BY-SA 3.0
2012-10-18T20:49:38.077Z
2012-10-18T20:49:38.077Z
Suresh Venkat
<p>I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network flows, edge/vertex cover, travelling salesman etc.) I know that some of them are NP-hard, but the point being that they can be 'framed as a linear program' if not solved optimally.</p>

<p>That got me thinking: We've always been taught systems of linear equations, linear algebra all throughout school/college. And seeing the power of LPs for expressing various algorithms it's kinda fascinating.</p>

<p>Question: Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science? I do understand that they help simplify the understanding and are computationally tractable most of the times but is that it? How good is this 'approximation'? Are we over-simplifying and are the results still meaningful in practice? Or is it just 'nature' i.e. the problems that are the most fascinating are indeed simply linear?</p>

<p>Would it be safe to safe that 'linear algebra/equations/programming' are of the corner stones of CS? If not then what would be a good contradiction? How often do we deal with non-linear stuff (I don't necessarily mean theoretically but also from a 'solveability' standpoint i.e. just saying it's NP doesn't cut it; there should be a good approximation to the problem and would it land up being linear?)</p>

CC BY-SA 3.0
2012-10-18T06:00:37.653Z
@downvoter: I'd really appreciate the reason for downvoting. This is a legitimate and inquisitive question
PhD
CC BY-SA 3.0
2012-10-18T09:16:31.710Z
I didn't downvote, but I don't see why tractability isn't a satisfying answer for you. There are some interesting precise senses in which non-convex problems are intractable eg. http://arxiv.org/abs/1210.0420 .
Colin McQuillan
CC BY-SA 3.0
2012-10-18T13:41:03.880Z
Downvoters may have [many reasons](http://meta.cstheory.stackexchange.com/questions/1395/about-some-criticisms-against-down-votes-without-explanations) why they choose not to comment.
Tyson Williams
CC BY-SA 3.0
2012-10-18T18:37:35.703Z
one way to look at it is that any NP problem can be reduced to integer programming in polynomial time, and then the integer programming problem can be relaxed. but we do use spectral techniques and SDP relaxations, which are quadratic optimization problems that are efficiently solvable.
Sasho Nikolov
CC BY-SA 3.0
2012-10-19T22:24:30.190Z
What does “linear systems” in this question mean?
Tsuyoshi Ito
CC BY-SA 3.0
2012-10-19T23:40:39.990Z
linear systems are found all over _science_ period.... its a simplification that gets surprisingly high mileage.... it seems a small corollary to [the unreasonable effectiveness of mathematics in the natural sciences](http://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness_of_Mathematics_in_the_Natural_Sciences) .. apparently CS fits this category of "natural sciences".... it is closely allied with physics, arguably increasingly so all the time [eg shrinking transistors, heat dissipation, low level QM, study of energy consumption, entropy, etc]....
vzn
CC BY-SA 4.0
2022-07-08T01:26:59.423Z
If one includes integer linear programs under "linear systems", as the post seems to implicitly suggest (e.g. by considering traveling salesman), then the premise of the post seems to be a fundamental misconception.  integer linear programs are not linear systems, any more than any other NP-hard problem formulation is a linear system.
Neal Young
<optimization><big-picture><linear-programming><linear-equations>
How/Why are linear systems so crucial to computer science?
PhD
# How/Why are linear systems so crucial to computer science?

(Asked by: username_0 on 2012-10-18)

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network flows, edge/vertex cover, travelling salesman etc.) I know that some of them are NP-hard, but the point being that they can be 'framed as a linear program' if not solved optimally.

That got me thinking: We've always been taught systems of linear equations, linear algebra all throughout school/college. And seeing the power of LPs for expressing various algorithms it's kinda fascinating.

Question: Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science? I do understand that they help simplify the understanding and are computationally tractable most of the times but is that it? How good is this 'approximation'? Are we over-simplifying and are the results still meaningful in practice? Or is it just 'nature' i.e. the problems that are the most fascinating are indeed simply linear?

Would it be safe to safe that 'linear algebra/equations/programming' are of the corner stones of CS? If not then what would be a good contradiction? How often do we deal with non-linear stuff (I don't necessarily mean theoretically but also from a 'solveability' standpoint i.e. just saying it's NP doesn't cut it; there should be a good approximation to the problem and would it land up being linear?)

**Tags:** optimization, big-picture, linear-programming, linear-equations

> **Comments:**
> **username_0**: @downvoter: I'd really appreciate the reason for downvoting. This is a legitimate and inquisitive question  
> **username_1**: I didn't downvote, but I don't see why tractability isn't a satisfying answer for you. There are some interesting precise senses in which non-convex problems are intractable eg. http://arxiv.org/abs/1210.0420 .  
> **username_2**: Downvoters may have [many reasons](http://meta.cstheory.stackexchange.com/questions/1395/about-some-criticisms-against-down-votes-without-explanations) why they choose not to comment.  
> **username_3**: one way to look at it is that any NP problem can be reduced to integer programming in polynomial time, and then the integer programming problem can be relaxed. but we do use spectral techniques and SDP relaxations, which are quadratic optimization problems that are efficiently solvable.  
> **username_4**: What does “linear systems” in this question mean?  
> **username_5**: linear systems are found all over _science_ period.... its a simplification that gets surprisingly high mileage.... it seems a small corollary to [the unreasonable effectiveness of mathematics in the natural sciences](http://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness_of_Mathematics_in_the_Natural_Sciences) .. apparently CS fits this category of "natural sciences".... it is closely allied with physics, arguably increasingly so all the time [eg shrinking transistors, heat dissipation, low level QM, study of energy consumption, entropy, etc]....  
> **username_6**: If one includes integer linear programs under "linear systems", as the post seems to implicitly suggest (e.g. by considering traveling salesman), then the premise of the post seems to be a fundamental misconception.  integer linear programs are not linear systems, any more than any other NP-hard problem formulation is a linear system.  

---

## 3 answers

### Answer by username_8 on 2012-10-18. Score: 13 | Accepted answer

The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability.

Perhaps what is more relevant is "why do linear systems admit tractable solutions ?" which is not exactly what you asked, but is related. One perspective on this is composability. Since the defining property of a linear system is that $f(x + y) = f(x) + f(y)$, this imparts a kind of "memorylessness" to the system. To build up a solution to a problem I can focus on individual pieces and combine them with no penalty. Indeed, the premise of most algorithms for flow is precisely that.

This memorylessness imparts efficiency: I can break things into pieces, or work iteratively, and I don't lose by virtue of doing so. I can still make bad decisions (c.f. greedy algorithms) but the act of splitting things up itself doesn't hurt me.

This is one reason why linearity has such power. There are probably many others.

> **Comments:**
> **username_10**: I like this answer but to those that argue that linear programming is not the boundary, I respond with: "it's P-complete!" ;).  
> **username_8**: Yes but is it the case that (for example) SDPs are not ?  
> **username_10**: We don't have to have a single boundary, and some boundaries of P (say quadratic programming with positive semi-definite matrix for the squared terms) do seem more general. I didn't mean to disagree, was just pointing out that the boundary is more a matter of taste when picking between P-complete problems.  

---

### Answer by username_7 on 2012-10-18. Score: 6

"*Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science?"*

Here is a partial answer in my mind:
I think it is because nature is abound with objects/phenomena - representable by functions which albeit being nonlinear on their operands, are actually members of linear spaces. The wave functions in a Hilbert space, the components in a fourier spectrum, polynomial rings, stochastic processes - they all behave in that fashion.
Even very general definitions of curved spaces are built out of composing small charts of flat spaces ( manifolds, Riemann surfaces, .. ).
Moreover, nature is full of symmetries and studying symmetries invariably gets into study of linear operators (representation theory, in my mind, is creeping into many areas of computer science ever so ubiquitously).

These are in addition to the cases where the operators themselves are linear in nature.

A large fraction of problems for which we need computer programs, arise either directly as, or are abstracted from, naturally occuring phenomena. Perhaps studying/solving linear systems shouldn't be a great deal of surprise, after all?

> **Comments:**
> **username_8**: Ah yes, the wonderful joys of lifting maps.  

---

### Answer by username_9 on 2022-07-07. Score: 2

I think all answers here are pretty good and linear systems admitting tractable solutions is definitely a big factor. I also like username_7's answer about the ubiquity of linear spaces. But I also feel the need to point out that the instinct to ask this question is certainly not misplaced. Since the question employed some physical intuition, I think some physics context might be useful to illustrate why this is actually a really good question and why there's a slight caveat to the answers.

It is after all true that one of the big reasons why we think quantum mechanics is incomplete, is precisely because the Schrödinger equation, which governs quantum dynamics, is linear. Linear systems do not admit chaos, non-linear systems do. So it would seem that a purely quantum mechanical universe is one that is void of chaos, which doesn't correspond to our universe (quantum chaos is an open question in physics). This has implications for the question of whether quantum computers can be hoped to truly simulate as much as some hope them to, since quantum computers can be thought of as efficient in simulating nature because we don't have to simulate the "quantumness" (this is a bit of an oversimplification, but true to a certain extent).

Even if we look at machine learning, it seems to be the case that non-linear neural nets are needed to be particularly good at learning. Linear systems simply don't do as well here.

So while most of our universe seems perfectly well described by approximations of linearity, it may just very well be that we're missing out on *some* structure by not being better at computing non-linear systems.


---

