5 ms·

One interesting question is how to implement linear algebra for the case of binary variables x_i in {0,1} or x_i in {-1,0,+1} as opposed to having continuous va

by ddmd 5y ago

One interesting question is how to implement linear algebra for the case of binary variables x_i in {0,1} or x_i in {-1,0,+1} as opposed to having continuous variables. Of course, it will be somewhat different theory but the general properties should be analogous to those of standard linear algebra. For example, dot product should express the notion of orthogonality, there should be well defined distance etc. I am not sure that such a theory exists at all but if yes then I am curious if there exist implementations.

yobbo 5y ago
You might find what you're looking for if you google "linear systems over finite fields" or "integer linear systems".
tlarkworthy 5y ago
Mixed integer programming? Here is a browser version https://observablehq.com/@tomlarkworthy/mip https://observablehq.com/@tomlarkworthy/mip
tryingtopost 5y ago
It exists. Linear algebra is defined over finite fields. In the case of {0, 1} that is Z_2 and the case of { -1, 0, + 1 } that is Z_3.
- ouid 5y ago
  There are algorithms which fail over GF(2). Gram-schmidt, for instance.
dragontamer 5y ago
Discrete mathematics theory is possibly more difficult than the set of complex numbers. Case in point: linear optimization across the reals/complex field is solved with the simplex algorithm. Boolean optimization in contrast, is NP-complete since its equivalent to the knapsack problem (0 for "don't pack the object" and 1 for "do pack the object". Each object has a space it takes up + a value. Optimizing on value is NP-complete). Literally more difficult from a computational perspective than its Real/Complex analogue, and __provably__ so. I'm enjoying my personal studies into Binary Decision Diagrams: the data-structures that are used in Verilog / VHDL synthesizers, libraries, CPU-design, verification (etc. etc.) to encode boolean truth tables and yes... tackle NP-complete and even #P-complete problems (#P complete is "determine the number of solutions" to an NP complete problem. Knights Tours aren't NP complete but... see the paper for an example of #P-like counting problems: "The Number of Knight's Tours Equals 33,439,123,484,294": https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.528&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45...). The boolean truth table for a 64x64-bit multiplication is 128-bits of input and 128-bits of output. That's 2^253 bytes of storage under a naive scheme, which is clearly unworkable. Binary Decision Diagrams make it possible to store, compute, and "think" about these functions at a high level. (Ex: counting solutions, finding the 1st solution, combining truth tables together, etc. etc.) Knuth's TAOCP Volume 4A has been a good introduction to the theory, but Knuth's writing style is so difficult sometimes. I'm probably going to buy a supplemental textbook on the subject...
- ddmd 5y ago
  > Discrete mathematics theory is possibly more difficult than the set of complex numbers. Probably it is so because in continuous case there is the luxury of having enough points between any other points. In discrete case you are much more constrained, for example, you cannot choose a point between 0 and 1, and what is the length of the diagonal of a binary cube or angle between its two hyper-planes? Sometimes these notions can be naturally defined but in other cases the formal theory is not so natural. By the way, an interesting question is how complex boolean numbers could be defined (naturally).
  - dragontamer 5y ago
    > By the way, an interesting question is how complex boolean numbers could be defined (naturally). Ever work with GF(2^x) extension fields? For a good practical application of "binary complex numbers" (aka: GF(2^x) extension fields), see Reed Solomon error correction codes. EDIT: NASA's Reed Solomon code tutorial is an excellent, "casual", introduction to the subject. (Very little math theory involved: mostly sticks to the "final math" so to speak, focusing on the Reed Solomon error correction aspects). Once you understand how Reed Solomon codes are used, you can then more easily go into the theory of how it relates to GF extension fields, and how those GF-extension fields are similar to complex numbers made up of 0s and 1s.
  - le-mark 5y ago
    Very interesting thank you. Is there an area of study that considers bit strings as one dimensional stochastic processes?
    - dragontamer 5y ago
      I'd have to imagine that's "just" a 2-valued discrete Fourier transform / discrete cosine transform.
  - dhosek 5y ago
    >By the way, an interesting question is how complex boolean numbers could be defined (naturally). Booleans act as a weird sort of field where there's no addition¹ and both ∧ and ∨ act as multiplication operators with F≡0 for ∧ and T≡0 for ∨. From this, you can build up the 3×3 tables for each relation to derive that if we add a third value to the boolean arithmetic, say, i, that T ∨ i = T F ∨ i = i i ∨ i = F and F ∧ i = F T ∧ i = i i ∧ i = T No other values are possible without destroying the group operations on ∧ and ∨ since we can't have a multiplication operation between two non-zero values give zero and within the non-zero members of the group, we cannot have repeated elements in any row or column. ——— 1. This isn't strictly true since we can actually define two possible addition operators, each associated with ∧ and ∨. The associated addition for ∧ would be exclusive or (A + B = T iff A ≠ B) and the associated addition for ∨ would be if and only if (A + B = T iff A = B). The extension of these groups to include i is left as an exercise for the reader, but yes, there is only one possible solution.

by ddmd 5y ago

yobbo 5y ago

You might find what you're looking for if you google "linear systems over finite fields" or "integer linear systems".

tlarkworthy 5y ago

Mixed integer programming? Here is a browser version https://observablehq.com/@tomlarkworthy/mip https://observablehq.com/@tomlarkworthy/mip

tryingtopost 5y ago

It exists. Linear algebra is defined over finite fields. In the case of {0, 1} that is Z_2 and the case of { -1, 0, + 1 } that is Z_3.

ouid 5y ago
There are algorithms which fail over GF(2). Gram-schmidt, for instance.

dragontamer 5y ago

Discrete mathematics theory is possibly more difficult than the set of complex numbers. Case in point: linear optimization across the reals/complex field is solved with the simplex algorithm. Boolean optimization in contrast, is NP-complete since its equivalent to the knapsack problem (0 for "don't pack the object" and 1 for "do pack the object". Each object has a space it takes up + a value. Optimizing on value is NP-complete). Literally more difficult from a computational perspective than its Real/Complex analogue, and __provably__ so. I'm enjoying my personal studies into Binary Decision Diagrams: the data-structures that are used in Verilog / VHDL synthesizers, libraries, CPU-design, verification (etc. etc.) to encode boolean truth tables and yes... tackle NP-complete and even #P-complete problems (#P complete is "determine the number of solutions" to an NP complete problem. Knights Tours aren't NP complete but... see the paper for an example of #P-like counting problems: "The Number of Knight's Tours Equals 33,439,123,484,294": https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.528&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45...). The boolean truth table for a 64x64-bit multiplication is 128-bits of input and 128-bits of output. That's 2^253 bytes of storage under a naive scheme, which is clearly unworkable. Binary Decision Diagrams make it possible to store, compute, and "think" about these functions at a high level. (Ex: counting solutions, finding the 1st solution, combining truth tables together, etc. etc.) Knuth's TAOCP Volume 4A has been a good introduction to the theory, but Knuth's writing style is so difficult sometimes. I'm probably going to buy a supplemental textbook on the subject...

ddmd 5y ago
> Discrete mathematics theory is possibly more difficult than the set of complex numbers. Probably it is so because in continuous case there is the luxury of having enough points between any other points. In discrete case you are much more constrained, for example, you cannot choose a point between 0 and 1, and what is the length of the diagonal of a binary cube or angle between its two hyper-planes? Sometimes these notions can be naturally defined but in other cases the formal theory is not so natural. By the way, an interesting question is how complex boolean numbers could be defined (naturally).
- dragontamer 5y ago
  > By the way, an interesting question is how complex boolean numbers could be defined (naturally). Ever work with GF(2^x) extension fields? For a good practical application of "binary complex numbers" (aka: GF(2^x) extension fields), see Reed Solomon error correction codes. EDIT: NASA's Reed Solomon code tutorial is an excellent, "casual", introduction to the subject. (Very little math theory involved: mostly sticks to the "final math" so to speak, focusing on the Reed Solomon error correction aspects). Once you understand how Reed Solomon codes are used, you can then more easily go into the theory of how it relates to GF extension fields, and how those GF-extension fields are similar to complex numbers made up of 0s and 1s.
- le-mark 5y ago
  Very interesting thank you. Is there an area of study that considers bit strings as one dimensional stochastic processes?
  - dragontamer 5y ago
    I'd have to imagine that's "just" a 2-valued discrete Fourier transform / discrete cosine transform.
- dhosek 5y ago
  >By the way, an interesting question is how complex boolean numbers could be defined (naturally). Booleans act as a weird sort of field where there's no addition¹ and both ∧ and ∨ act as multiplication operators with F≡0 for ∧ and T≡0 for ∨. From this, you can build up the 3×3 tables for each relation to derive that if we add a third value to the boolean arithmetic, say, i, that T ∨ i = T F ∨ i = i i ∨ i = F and F ∧ i = F T ∧ i = i i ∧ i = T No other values are possible without destroying the group operations on ∧ and ∨ since we can't have a multiplication operation between two non-zero values give zero and within the non-zero members of the group, we cannot have repeated elements in any row or column. ——— 1. This isn't strictly true since we can actually define two possible addition operators, each associated with ∧ and ∨. The associated addition for ∧ would be exclusive or (A + B = T iff A ≠ B) and the associated addition for ∨ would be if and only if (A + B = T iff A = B). The extension of these groups to include i is left as an exercise for the reader, but yes, there is only one possible solution.