1
vote
2answers
39 views

Number of solutions for inqeuality

Is there a way we can determine number of solutions for equation $$x*y < d$$ where d is constant and x & y are positive integers greater than 1. I am not interested in actual values, but ...
0
votes
0answers
13 views

Matrix Partial Derivative?? NMF Multiplicative update rules

Recently, I read Lee & Seung's work on Nonnegative Matrix Factorization. But I have problem with the update rule: The object function is minimize: $\|V - MH \|$ with respect to M and H, subject ...
0
votes
0answers
16 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
-1
votes
0answers
32 views

Checking if integer solutions exist

I have a linear equation $\alpha_1a_1+\alpha_2a_2+\dots=\beta$. I only need to check is there exists α1,α2... such that all are greater than or equal to zero. I am a computer science student , i got ...
5
votes
0answers
75 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
4
votes
1answer
44 views

Randomly generate an matrix $A$ s.t. $A^m = I$

Fixed $n$, I want to randomly generate a $n \times n$ real matrix $A$ from the set: $\{A \in \mathcal{M}_{n \times n}(\mathbb{R}): \exists m \in \mathbb{N} \mbox{ s.t. } A^m = I\}$ I think I should ...
1
vote
1answer
31 views

matrix row/col mapping

Many square matrices are symmetric. i.e. $a_{i,j}=a_{j,i}$ For such matrices, we can only store the upper triangle elements, i.e. any $a_{i,j}$ for which $i<=j$. Assume a 10x10 matrix. Using this ...
2
votes
2answers
44 views

Solve linear equation system $A'Ax=A'Bz$

For $A$ and $B$ known matrices which are not square matrices, I have the following equation sistem i would like to solve numerically \begin{equation} A'Ax=A'Bz \end{equation} I want to know which is a ...
2
votes
2answers
65 views

Avoid dividing by zero with just variables and basic operators

I am working on stats for a sports team, and one of the stats I have the ratio of Shots and Shots on Target (Which I call ...
1
vote
1answer
25 views

Fast method to detect if a circulant matrix is singular

I have to write some code to detect if a large number of smallish (less than 20 by 20) square 0-1 matrices are singular over $\mathbb{R}$. As a circulant matrix is defined by its first row and its ...
2
votes
2answers
52 views

Linear Diophantine equation in two variables with additional constraints

Given, $$aX + bY = c$$ where, $$c > b > a > 0;\quad X, Y > 0;\quad b\nmid c, a\nmid c$$ I want to find out if a solution exists as efficiently as possible (I'm not interested ...
0
votes
1answer
58 views

How to tell if there exists a vector orthogonal to half your vectors

Given a set of $N$ vectors each with $n$ entries from the integers. How can you determine efficiently if there is any non-zero vector in $\mathbb{R}^n$ which is orthogonal to half of them?
1
vote
2answers
107 views

Flood algorithm - find polygon containing a given point.

I have some code that represents a set of a set of interconnected line segments in 2D, in pseudo-code it'd be like this: ...
1
vote
1answer
81 views

Solve $Mx = 0$ for $x$

Given an $m$ by $n$ matrix $M$ whose elements are $0$ or $1$, is there an efficient way of finding a vector $x \ne 0$ whose are elements are from $-1,0,1$ such that $Mx = 0$, or even determining if ...
0
votes
0answers
48 views

Strassen's Matrix Multiplication Example Problem

How to multiply two matrices using strassen's matrix multiplication.I have only learned the theory part but i cannot find any examples on the net. Could some one explain with two 2X2 Matrices.
29
votes
6answers
2k views

The milk sharing problem

I found a book with math quizzes. It was my father's when he was young. I encountered a problem with the following quiz. I solved it, but I wonder, is there a faster way to do it? If so, how can I ...
0
votes
0answers
25 views

Levenberg-Marquardt algorithm

Does anyone know if the Levenberg-Marquardt algorithm used to solve non-linear least squares problems has any regularization process?
1
vote
0answers
40 views

Gauss-seidel and implicit method

I have a matrix $\mathbf{X}$ and I want to apply a function $f_{ij}$ to each entry of it, until convergence is satisfied. If a value is known in this matrix, then the $f_{ij}$ at this point may be the ...
2
votes
0answers
406 views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
6
votes
0answers
103 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
1
vote
1answer
60 views

Efficient Algorithm for Generalized Sylvester's Equation

Is there an efficient computational algorithm for solving the generalized Sylvester's equation: $\displaystyle \sum_{i=1}^{n}A_{i}XB_{i}=C$ The conventional Kronecker product approach to solve this ...
1
vote
1answer
73 views

Proof for existence of exactly one solution for the number of marbles in each box

There are four boxes A, B, C and D containing marbles. Two boxes are randomly selected and the number of marbles in each box is summarized. This procedure is repeated five times with the ...
0
votes
1answer
69 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
0
votes
0answers
39 views

Operation count for Tridiagonal System

What is the operation count for solving the tridiagonal system $Ax=b$. I would guess it is $O(n^2)$ because all we are doing is making one sub-diagonal zero all the way across giving us $t(n)=n$ and ...
3
votes
0answers
62 views

How to quickly approximate the eigenvectors of a symmetric matrix

Given a symmetric $n \times n$ matrix $A$, is there any algorithm that can quickly approximate all of its eigenvectors? By "quickly", I mean with time complexity less than $\mathcal{O}(n^3)$.
2
votes
0answers
79 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
1
vote
2answers
40 views

Solving system of linear eqaution in special cases

I have to solve for $Ax=B$. Here the diagonal elements of $A$ are $-1$ and all other elements are $1$. $A$ is $n \times n$ matrix . In this special case can we solve for $x$ quickly? EDIT: quick is ...
1
vote
1answer
108 views

Computing the number of positive and negative eigenvalues

Given a $n \times n$ symmetric matrix $A$ with integers as entries I would like to compute the number of strictly negative $\rm{nn}(A)$ and positive $\rm{np}(A)$ eigenvalues of $A.$ My question is ...
1
vote
1answer
429 views

Prove Solving a Lower Triangular Matrix By Forward Substitution is Backwards Stable

I'm taking a class in scientific computing and we are working on proving stability of certain algorithms. Unfortunately, at this stage, everything is proof-based, and I have little to no experience in ...
0
votes
0answers
36 views

Probability, linear independence and study of variant of Lights Out

Using Arduino, some leds and pushbuttons I've created a simple variant of the mathematically popular game "Lights Out". In my variant, the starting configuration is always all lights on; what changes ...
1
vote
1answer
55 views

Meet of lines in n-dimension.

I am searching for a general approach to use in a script for determining if two n-dimensional lines represented by one point and their direction vector are skew, parallel, intersecting or identical. ...
0
votes
2answers
85 views

modulo 2 linear equation algorithm

Given is a set of modulo 2 linear equations. I'm looking for a performant algorithm that solves these linear equations. The Row Reduction to the ...
0
votes
1answer
44 views

Project path on tiled surface

Here is the description. I do present earth as a Sphere. I've splitted the earth on tiles starting from latitude=0, longitude=0. Tile is a rectangle ~$50\times50$ kilometers. Tiles are "planar". ...
0
votes
1answer
95 views

Payment problem

I'm looking for an algorithm, which can solve the following problem: There is a basket, containing (n) products, paired with a value, which shows how much money is required to cover them. E.g ...
2
votes
1answer
142 views

Find a projection of a $k$-simplex with minimal “radius”

Let $S$ be a $k$-simplex in $\mathbb{R}^k$. I'd like to find a hyperplane $P$ that passes through the origin such that projections of vertices of $S$ onto $P$ are as close as possible to the origin ...
2
votes
1answer
54 views

How to compute $x$ and $y$

How can one find in an efficient way $x,y \in \mathbb{Z}$ with max$\{|x|,|y|\} > 0$ as small as possible such that $\mid \pi x + e y \mid < 10^{-4}$ ? I have reduced the following lattice ...
0
votes
2answers
227 views

Find a solution to any single-variable equation

I know it is not possible to solve any equation of fifth degree and higher "using only a finite combination of the arithmetic operations and radicals in terms of the coefficients" (see on Wikipedia). ...
1
vote
1answer
35 views

Question about linear systems of equations

Let $X=\{x_1,\cdots,x_n\}$ be a set of variables in $\mathbb{R}$. Let $S_1$ be a set of linear equations of the form $a_1 x_1+\cdots+a_n x_n=b$ that are independent. Let $k_1=|S_1|<n$ where $|S_1|$ ...
0
votes
0answers
50 views

Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1, \ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors, assumed affinely independent (in the field of reals). Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ ...
1
vote
1answer
48 views

Three-dimensional positioning given the distances from well-known fixed stations

I need to compute the position of a static object based on the distance to multiple fixed stations (it the same thing we do to calculate the GPS receiver position based on the satellites position). I ...
2
votes
1answer
89 views

The relationship between fisher information and EM algorithm?

I wonder what is the relationship between fisher information and EM algorithm? When I read papers about EM algorithm, people sometimes discussed about fisher information, and there are algorithms ...
2
votes
1answer
78 views

Proof of correctness of Putzers algorithm

I have a question regarding the proof (seen below) of Putzers algorithm for matrix exponentiation. It's written by our danish lecturer at the university, so I translated the important parts into ...
0
votes
1answer
82 views

Collinearity in n dimensions

What is the best way to check if $m$ points are collinear in $n$ dimensions? I mean I have $p_1=(3, 4, 5, 2),\quad p_2=(6, 3, 4, 2),\quad p_3=(5, 3, 5, 6),\quad p_4=(4, 2, 7, 4)$ or ...
2
votes
1answer
411 views

Algorithm for solving a linear system of equations with external constraints?

I am trying to device an algorithm for rapidly solving systems of linear equations/inequalities with constraints, without necessarily relying on existing LP algorithms, such as Simplex. The reason I ...
1
vote
0answers
20 views

Filtering matrices based on model

This should be quite easy for someone with linear-algebra skills, sorry if this sounds too basic :-) I am looking for guidance to construct an efficient algorithm to filter a list of matrices based on ...
6
votes
2answers
837 views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
2
votes
0answers
125 views

all eigenvalues of a large sparse symmetric matrix

my question is similar to how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors however i wish to be more concrete and ask if one can, on a standard PC (e.g. a ...
0
votes
0answers
66 views

backward stability of full svd decomposition

Why is it impossible for the full SVD decomposition of a matrix A to be a backward stable algorithm? This was mentioned in one of my readings but it doesn't explain why.
5
votes
2answers
152 views

Sparse basis for linear subspace

Suppose I have a linear subspace of some vector space, e.g. described as the column space of some big matrix. How would I algorithmically find a basis of that same subspace where the basis matrix is ...
5
votes
1answer
110 views

Maximal subset with rank $k$

I'm trying to solve the following problem for an algorithm I'm trying to develop and I couldn't find anything helpful in scholar google. Here is the question: Suppose I have a set of $N$ vectors ...