# Questions tagged [linear-algebra]

The tag has no usage guidance.

216 questions
Filter by
Sorted by
Tagged with
21 views

### Kalman Filter - Dynamic System

Given the two equations below \begin{aligned} 300x + 400y &= 700 \\ 100x + 133y &= 233 \end{aligned} how can one find a solution for those equations using Kalman filter (and suppose the ...
34 views

### Bound on the number of signed sums of a non-zero vector that can all equal zero

Let $u$ be a real vector of $m$ entries, and $A$ be a $\pm 1$ matrix of dimension $N\times m$, and real rank $\operatorname{rank}(A) = r$. What are some conditions on $A$ (e.g. in terms of its rank $r$...
22 views

### can similarity transformation be linear transformation?

Learning Computer Graphics - Can similarity transformation be linear transformation? Similarity T is a rigid transformation (translation and rotations) with uniform scaling. so I guess a similarity ...
44 views

### What is this linear optimization problem?

Given a $d$-dimensional vector $v = (v_1,\dots,v_d) \in \Bbb{R}^d$, we define $f(v) = \min_{i\in [d]} \{v_i\}$ to be the smallest coordinate of $v$. Let $v^1,\dots,v^n \in \Bbb{R}^d_{\ge 0}$ be non-...
25 views

### How to eliminate « a priori » all vectors in a list of vectors whose scalar product with a given vector is zero without calculating the product

How to eliminate « a priori » all vectors in a list of vectors, whose scalar product with a given vector is zero, without actually calculating the product ? One solution would be to store the ...
41 views

### Recommendations on where to learn and practice linear programming?

[CLOSED] Thanks! I am studying Linear Programming in college but I am facing some difficulties to assimilate some concepts. So do you have any recommendations of materials to learn or practice Linear ...
24 views

### Lower bound on number of zero columns in matrix

I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...
25 views

### Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
1k views

### Why is the probability of a false positive not 0 for Freivald's Algorithm?

Freivald's algorithm (see the wiki) is a randomized algorithm for verifying whether the product of two $n \times n$-matrices $A$ and $B$ yields a given matrix $C$ (i.e. $AB = C$). The way this task is ...
92 views

### How to setup the Bellman Equation as a linear system of equation

I was watching a video on Reinforcement Learning by Andrew Ng, and at about minute 23 of the video he mentions that we can represent the Bellman equation as a linear system of equations. I am talking ...
17 views

### Calculating the shortest vector between a vector and a truncated cone

I am trying to understand a certain implementation of calculating the shortest vector between a vector and a truncated cone in 3D. The original idea is introduced in this paper. So if we have two ...
121 views

### Fast computing of a matrix power for large integer values in C++

I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix. My objective is to compute the power of the squared matrix ...
30 views

### Least probability of collisions using rgb as a hash map

I need to rewrite a short utility library, to get it working with the Brave browser (My actual question isn't about brave per se.) canvas-color-tracker - example of it being used and src/index.js is ...
47 views

45 views

### Coordinate descent for Lasso, Question about algorithm

I'm not sure why the algorithm computes $c_k$ with $\sum_{j \neq k} w_j x_{i, j}$. Why does one need to ignore the $k^{th}$ feature here? I'm not sure how this is derived. Is this the result of taking ...
51 views

41 views

### Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same

Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct. Question: What would be the complexity of its inversion? On the ...
20 views

### Math behind Multi-class linear discriminate analysis (LDA)

I have a question about Linear Discriminant Analysis (LDA) for the purpose of Dimensionality Reduction. So I understand for the algorithm to calculate for $k$ projection vector(s) you need to ...
147 views

### Applying SVD compression to integral point images

Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
27 views

### Minimum basis for the nullspace of sparse matrices

Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
63 views

I'm given an array $A = [a_1, a_2, ....a_n]$ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$. Now, I'm given $q$ queries in the form of $... 2answers 885 views ### Count number of pairs of elements whose product is a perfect square Given two arrays whose elements lie between$[1,10^5]$and the size of arrays is$[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a ... 1answer 49 views ### Given a set of integers$D$and a positive value$P$, find an algorithm to find set of integers satisfying a condition Given a set of positive integers :$ \\ D = \{ D_1, D_2, ..., D_n\}$and a non-negative integer$P$, where$P$is divisible by every element in$D$, then find ... 0answers 19 views ### Are there practical usage of determinants in numerical simulation? I know the historical importance of the link between linear systems and determinants. I also know that determinants have a beautiful connection with non-singular matrices, i.e., if a matrix is non-... 0answers 45 views ### What is the complexity of finding e^(A) for a Hermitian matrix A? If A is a hermitian matrix of size NxN .What is the order of no. of steps required to compute e^(A).How to prove it? 0answers 21 views ### Minimal subset of rows that generate smaller polyhedron Given a matrix$[A|B]$I want to find a minimal matrix$[A'|B'] \subseteq [A|B]$(i.e. the rows in$[A'|B']$are also in$[A|B]$) such that$A'x < B' \Rightarrow Ax < B$. Geometrically, I want ... 0answers 36 views ### Given a system in$\mathbb{F}_2$in RREF, how do I find a solution of minimal norm? I have a$12 \times 12$(so not really large) system of linear equations in$\mathbb{F}_2$which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ... 0answers 31 views ### How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)? Given $$a_1 X_1 + \dots + a_n X_n = b$$ where$a_i, b \in \Bbb{Z}$. How do you come up with a clearer picture of the solution set in polynomial time. Also, what I really want is to do the above,... 0answers 15 views ### Convergence of Conjugate gradient method I have implemented my own matrix library in Java to solve fluid simulations. So I have also implemented the conjugate gradient method and I got a little bit confused. What I have done to test my CG-... 1answer 68 views ### Recover boolean vector from dot products Question: I want to determine a boolean vector$b \in \{0,1\}^n$consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product ... 1answer 52 views ### Underlying codes for Niederreiter cryptosystems Niederreiter cryptosystem is usually described by a parity check matrix$H$over$\mathbb{F}_{2^n}$. The minimum distance$d$is given by$d := min\lbrace k \text{ such that there are $k$ linearly ...
I'm trying find an optimization for an equation related to theorem 3.5.7 from "Finite Markov Chains" by Kemeny and Snell (1976). The theorem is: $$H=(N-I)N_{dg}^{-1}$$ Where $N_{dg}$ is a diagonal ...